当前位置:网站首页>快速排序

快速排序

2020-11-27 12:07:51 不擅长纵横的捭阖家

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. 快速排序高阶

3.1 双指针

 通过使用双指针的方式进行排序入,下图所示:

代码如下:

template <typename T>
    int __partition2(T arr[], int l, int r){

        swap( arr[l] , arr[rand()%(r-l+1)+l] );
        T v = arr[l];

        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i] < v )
                i ++;

            while( j >= l+1 && arr[j] > v )
                j --;

            if( i > j )
                break;

            swap( arr[i] , arr[j] );
            i ++;
            j --;
        }

        swap( arr[l] , arr[j]);

        return j;
    }


    template <typename T>
    void __quickSort2(T arr[],int l,int r){
//        出现异常
        if (r<l){
            insertSort(arr,r,l);
            return;
        }

        int p = __partition2(arr,l,r);
        __quickSort2(arr,l,p-1);
        __quickSort2(arr,p+1,r);
    }



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

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



    template <typename T>
    void insertSort(T arr,int l,int r){
        for (int i = l+1; i < r; ++i) {
            T e  = arr[i];
            int j;
            for (j = i; j > 0 && arr[j-1]>e; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }

3.2 三路快速排序


如果 e<v,那么就和 lt+1位置上的元素进行互换。如果e>v,就和gt-1上的元素进行互换,同样的两边的索引,左边的++,右边的--。最后把第一个v的元素和lt上的元素进行互换。

代码如下:

 template <typename T>
    void __quickSort3(T arr[], int l, int r){
        if (r<l){
//            insertSort(arr,l,r);
            return;
        }

        swap(arr[l],arr[rand()%(r-l+1)+l]);
        T v = arr[l];

        int lt = l;
        int gt = r+1;
        int i = l+1;
        while (i<gt){
            if (arr[i]>v){
                swap(arr[i],arr[--gt]);
            }else if (arr[i]<v){
                swap(arr[i++],arr[++lt]);
            }else{
                i++;
            }
        }
        swap(arr[l],arr[lt]);
        __quickSort3(arr,l,lt-1);
        __quickSort3(arr,gt,r);
    }

    template <typename T>
    void quickSort3(T arr[],int n){

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

参考文献

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

版权声明
本文为[不擅长纵横的捭阖家]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sailorlee11/p/14030106.html