快速排序&三路快排(C++实现)

公共函数,用以测试数组相等

namespace SortCommon {
    bool ArrEqual(int arr1[], int arr2[], int n) {
        for (int i = 0; i < n; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

快速排序第一版,如果遇到重复元素较多的时候,复杂度会逼近O(N*N)

    // partition
    int Partition(int arr[], int l, int r) {
        // 优化,随机化选择标头v,即随机置换一个数据到头部,用作标头
        std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
        int v = arr[l];
        int j = l;
        // arr[l...j] 存储小于v的元素
        // arr[j+1....i) 存储大于等于v的元素
        for (int i = l + 1; i <= r; ++i) {
            if (arr[i] < v) {
                std::swap(arr[i], arr[j + 1]);
                ++j;
            }
        }
        std::swap(arr[j], arr[l]);
        return j;
    }

    void QuickSortAdaptor(int arr[], int l, int r) {
        if (l >= r) {
            return;
        }
        int p = Partition(arr, l, r);
        QuickSortAdaptor(arr, l, p);
        QuickSortAdaptor(arr, p + 1, r);
    }

    void QuickSort(int arr[], int n) {
        if (n <= 1) {
            return;
        }
        QuickSortAdaptor(arr, 0, n - 1);
    }

快速排序第二版,将与标头重复的元素“均匀”分到左右两边,解决重复元素过多导致的性能下降问题

   // partition优化1,将与标头v相同的元素“均匀”分布在左、右两边
    int Partition(int arr[], int l, int r) {
        // 优化,随机化选择v
        std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
        int v = arr[l];
        int i = l + 1;
        int j = r;
        // arr[l...i) 存储小于等于v的元素
        // arr(j....r] 存储大于等于v的元素
        while (true) {
            while (i <= r && arr[i] < v) {
                ++i;
            }
            while (j >= l && arr[j] > v) {
                --j;
            }
            if (i > j) {
                break;
            }
            std::swap(arr[i], arr[j]);
            ++i;
            --j;
        }
        return j;
    }

快速排序第三版,将重复元素单独分一段,即分成  <v, ==v, >v三段,即三路快排

    // partition优化2,将与标头v相同的元素单独分成一段,即三路快排
    std::pair<int, int> Partition3ways(int arr[], int l, int r) {
        // 优化,随机化选择标头v
        std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
        int v = arr[l];
        int lt = l;
        int gt = r + 1;
        int i = l + 1;
        // arr[l+1...lt] 存储 <v 的元素
        // arr[gt....r] 存储 >v 的元素
        // arr[lt+1....i) 存储 ==v 的元素
        while (i < gt) {
            if (arr[i] == v) {
                ++i;
                continue;
            } else if (arr[i] < v) {
                std::swap(arr[i], arr[lt + 1]);
                ++lt;
                ++i;
                continue;
            } else {
                std::swap(arr[i], arr[gt - 1]);
                --gt;
                continue;;
            }
        }
        std::swap(arr[l], arr[lt]);
        return {lt - 1, gt};
    }

    void QuickSortAdaptor3ways(int arr[], int l, int r) {
        if (l >= r) {
            return;
        }
        auto p = Partition3ways(arr, l, r);
        QuickSortAdaptor3ways(arr, l, p.first);
        QuickSortAdaptor3ways(arr, p.second, r);
    }

    // 三路快排
    void QuickSort3ways(int arr[], int n) {
        if (n <= 1) {
            return;
        }
        QuickSortAdaptor3ways(arr, 0, n - 1);
    }

测试

   void test() {
        int arr1[]{9, 3, 7, 6, 5, 1, 8, 2, 4};
        int arr1r[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        QuickSort(arr1, 9);
        assert(SortCommon::ArrEqual(arr1, arr1r, 9) == true);

        int arr2[]{1};
        int arr2r[]{1};
        QuickSort(arr2, 1);
        assert(SortCommon::ArrEqual(arr2, arr2r, 1));

        int arr3[]{2, 1};
        int arr3r[]{1, 2};
        QuickSort(arr3, 2);
        assert(SortCommon::ArrEqual(arr3, arr3r, 2));

        int arr4[]{5, 3, 3, 7, 5, 5, 5, 5, 1, 7, 2, 7, 7, 7, 7};
        int arr4r[]{1, 2, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7};
        QuickSort3ways(arr4, 15);
        assert(SortCommon::ArrEqual(arr4, arr4r, 15));

        int arr5[]{1, 3, 2};
        int arr5r[]{1, 2, 3};
        QuickSort(arr5, 3);
        assert(SortCommon::ArrEqual(arr5, arr5r, 3));

        return;
    }

 

上一篇:R语言广义线性模型GLM、多项式回归和广义可加模型GAM预测泰坦尼克号幸存者


下一篇:C++ 初始化函数的实现