快速排序&三路快排（C++实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速排序&三路快排（C++实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2978字，纯文字阅读大概需要5分钟。

内容图文

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

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;
    }

 

内容总结

以上是互联网集市为您收集整理的快速排序&三路快排（C++实现）全部内容，希望文章能够帮你解决快速排序&三路快排（C++实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---