1. 快排基础

?快速排序的要点是先找到第一个元素的最终的位置，如何寻找就如下图所示，找到比4小的数，在找到比4大的数。核心就是如何把4这个数挪到正确的位置上。

?下图中，l记录的是当前的元素，j记录<v和>v的分界点（对于j这个点上值多少不用去管），i是当前访问的元素。如果当e>v就直接放在后面。

?如果当e<v这种情况，就需要把e放在前面橙色的部分。方法很简单，e和j位置上的元素互换（直接将e放到j的位置），而j++就好。

?最后都结束了之后再把v这个元素放在j上。
初版代码如下：

//    对arr[l,,r]部分进行partition操作
//返回是一个索引 p  使得arr[l...p-1]  <  arr[p]   arr[p+1....r] > arr[p]
    template <typename T>
    int __partition(T arr[],int l,int r){
//        先把数保存下来
        T v = arr[l];
//        arr[l+1...j]  <  v   arr[j+1....r） > arr[j]
        int j = l;
        for (int i = l+1; i <= r; ++i) {
            if (arr[i] < v){
                swap(arr[j+1],arr[i]);
                j++;
            }
        }
        swap(arr[l],arr[j]);
        return j;
    }

//    内部快排接口 对arr[l...r]进行快速排序
    template <typename T>
    void __quickSort(T arr[],int l,int r){
//        出现异常
        if (l>=r){
            return;
        }

        int p = __partition(arr,l,r);
        __quickSort(arr,l,p-1);
        __quickSort(arr,p+1,r);
    }

    //    快速排序
    template <typename T>
    void quickSort(T arr[],int n){

        __quickSort(arr,0,n-1);
    }

和直接插入排序相比
结果如下：
quick order:0.01s
insertSort:2.941s

Process finished with exit code 0

2. 快排进阶

?当遇到近乎有序的数组时，快速排序会慢很多倍。
结果如下：
quick order:0.028s
insertSort:0s
?原因如下图，他和归并排序不一样的地方是归并排序始终是对数组一分为二。但是在快速排序中左右子树是不一定对称的。当遇到最差情况就是有序的数组左侧（或者右侧）子树是没有的，那么他会退化成o（n^2）。


解决方法也是很简单，即设置随机种子。随机选择一个元素把这个元素与第一个元素进行互换，这样可以降低退化成o（n^2）的可能性。

    //    对arr[l,,r]部分进行partition操作
//返回是一个索引 p  使得arr[l...p-1]  <  arr[p]   arr[p+1....r] > arr[p]
    template <typename T>
    int __partition(T arr[],int l,int r){
//        先把数保存下来
        swap(arr[l],arr[rand()%(r-l+1)+l]);
        T v = arr[l];
//        arr[l+1...j]  <  v   arr[j+1....r） > arr[j]
        int j = l;
        for (int i = l+1; i <= r; ++i) {
            if (arr[i] < v){
                swap(arr[j+1],arr[i]);
                j++;
            }
        }
        swap(arr[l],arr[j]);
        return j;
    }

//    内部快排接口 对arr[l...r]进行快速排序
    template <typename T>
    void __quickSort(T arr[],int l,int r){
//        出现异常
        if (r<l){
//            insertSort(arr,r-l+1);
            return;
        }

        int p = __partition(arr,l,r);
        __quickSort(arr,l,p-1);
        __quickSort(arr,p+1,r);
    }



    //    快速排序
    template <typename T>
    void quickSort(T arr[],int n){

        srand(time(NULL));
        __quickSort(arr,0,n-1);
    }

3. 快速排序高阶

?通过使用双指针的方式进行排序入，下图所示：

参考文献

[1]维基百科.快速排序[EB/OL].https://zh.wikipedia.org/wiki/快速排序,2020-10-10.

快速排序

原文：https://www.cnblogs.com/sailorlee11/p/14030106.html