排序算法

排序算法

排序算法之快速排序

Posted by Liangjf on April 9, 2019

排序算法之快速排序

1.快速排序介绍

快速排序在几种常用的O(N*logN)时间复杂度的排序方法中效率较高，而且核心思想也是分治法。

该方法的基本思想是：

  • 1．先从数列中取出一个数作为基准数(一般有取第一个/随机取)。
  • 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边(视升序排序还是降序排序)。
  • 3．再对左右区间重复第二步，直到各区间只有一个数(此时整个序列就是有序的)。

算法步骤：

单路快排

  • 1．i =L; j = p+1; (p是骚兵下标)将骚兵a[L]先取出保存下来，形成第一个待填位。
  • 2．i++由前向后找比它小的数，找到后也取出此数填到前一个待填位a[j]中,若没有跳过元素，且顺序不变。[l…p)
  • 3．j++由前向后找比它小的数，找到后取出此数填前一个待填位a[i]中，若没跳过元素，且顺序不变。[p+1…r]
  • 4．再重复执行2，3二步，直到整个数组有序。

双路快排

  • 1．i = l+1; j = r; (p是骚兵下标)将骚兵a[L]先取出保存下来，形成第一个待填位。
  • 2．i++由前向后找比它小的数，找到后也取出此数填到前一个待填位a[j]中,若没有跳过元素，且顺序不变。[l…p)
  • 3．j–由后向前找比它小的数，找到后取出此数填前一个待填位a[i]中，若没跳过元素，且顺序不变。[p+1…r]
  • 4．再重复执行2，3二步，直到整个数组有序。

2.快速排序算法从实现到优化

V1.0

template <typename T>
int __partition(T arr[], int l, int r) {
    T tmp = arr[l];

    int j = l;
    for(int i = l+1; i <= r; i++) {
        if(arr[i] < tmp) {
            j++;	//划分两个区间的下标，到最后停止时，就是划分好 ... < ...
            swap(arr[j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);	//最后... < ...时，把哨兵与划分区间下标的值交换，就是整个空间划分好
    return j;
}

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

快速排序是有哨兵的，这里以第一个元素为哨兵，如果这个哨兵每次都是刚好n-1大，那么快速排序就会退化为冒泡算法了，时间复杂度为n*n，因此从这里也看出来，快速排序可以优化的地方有：1.在接近有序时使用插入排序；2.不选择第一个元素为哨兵，使用随机元素，这也叫随机快速排序。

优化后的V2.0

template <typename T>
int __partition(T arr[], int l, int r) {
    //优化2：使用随机哨兵，进化为随即快速排序
    swap(arr[l], arr[rand()%(r-r+1)+l]);
    T tmp = arr[l];
    int j = l;
    for(int i = l+1; i <= r; i++) {
        if(arr[i] < tmp) {
            j++;	//划分两个区间的下标，到最后停止时，就是划分好 ... < ...
            swap(arr[j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);	//最后... < ...时，把哨兵与划分区间下标的值交换，就是整个空间划分好
    return j;
}

template <typename T>
void __QuickSort(T arr[], int l, int r) {
    /*if(l >= r) {
        return ;
    }*/
    //优化1：近乎有序时使用 插入排序 加快排序速度
    if(l >= r) {
        InsertSortFunc::InsertSort2(arr, 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);
}

经过优化后，通过随机哨兵，可以减少几率(只有1/n的几率)退化为nn或接近nn的时间复杂度。但是如果整个序列是有较多的相同元素，就会分成两个不平衡的区间，还是会拖慢排序的效率，因此出现双路快排，甚至三路快排，先看双路快排。

V3.0 双路快排

template <typename T>
int __partition(T arr[], int l, int r) {
    //优化2：使用随机哨兵，进化为随即快速排序
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T tmp = arr[l];
    int j = l;
    for(int i = l+1; i <= r; i++) {
        if(arr[i] < tmp) {
            j++;	//划分两个区间的下标，到最后停止时，就是划分好 ... < ...
            swap(arr[j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);	//最后... < ...时，把哨兵与划分区间下标的值交换，就是整个空间划分好
    return j;
}

template <typename T>
int __partition2(T arr[], int l, int r) {
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T tmp = arr[l];
    int i = l+1, j = r;
    while(true) {
        //从前往后找，l..->..r，比哨兵小不变，直到找到比哨兵大的值
        while(i <= r && arr[i] < tmp)
            i++;
        //从后往前找，l..<-..r，比哨兵大不变，直到找到比哨兵小的值
        while(j >= l+1 && arr[j] > tmp)
            j--;
        //停止标志，此时整个序列有序
        if(i > j)
            break;
        //由上两个区间都找到不满足while的值，交换二者
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    //最终交换哨兵与中间值
    swap(arr[l], arr[j]);
    return j;
}

template <typename T>
void __QuickSort(T arr[], int l, int r) {
    //优化1：近乎有序时使用 插入排序 加快排序速度
    /*if(l >= r)
        return;*/
    if(r - l <= 15 ) {
        InsertSortFunc::InsertSort(arr, l, r);
        return ;
    }
    //int p = __partition(arr, l , r);
    int p = __partition2(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);
}

双路快排，只有在元素小于(后一个区间)或大于(前一个区间)的时候才动作，因此不会变成不平衡的区间，所以不会退化成类似冒泡法的时间复杂度。但是还有更优的方案是三路快排，它对比单路/双路，查找对比的大小比较，而是一个区间，加快了比较排序的效率。

V3.0 三路快排

template <typename T>
void __QuickSort3Ways(T arr[], int l, int r) {
    if(r - l <= 15 ) {
        InsertSortFunc::InsertSort(arr, l, r);
        return ;
    }
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T tmp = arr[l];

    int lt = l; //arr[l+1...lt] < tmp
    int gt = r+1; //arr[gt...r] > tmp
    int i = l+1;
    while(i < gt) {
        if(arr[i] < tmp) {
            swap(arr[l], arr[lt+1]);
            i++;
            lt++;
        }
        else if(arr[i] > tmp) {
            swap(arr[i], arr[gt-1]);
            gt--;
        }
        else {
            i++;
        }
    }
    //最终交换哨兵与中间值
    swap(arr[l], arr[lt]);

    __QuickSort3Ways(arr, l, lt-1);
    __QuickSort3Ways(arr, gt, r);
}

template <typename T>
void QuickSort3Ways(T arr[], int n) {
    srand(time(NULL));
    __QuickSort3Ways(arr, 0, n-1);
}

3.快速排序多种场景下的测试

int N = 20000;
//稀疏数组，随机性大
int *arr1 = SortTestHelper::CreateRandomArray(N, 0, 1000000);
int *arr2 = SortTestHelper::copyIntArray(arr1, N);
int *arr3 = SortTestHelper::copyIntArray(arr1, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr1, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr2, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr3, N);
cout << endl;

//近乎有序
int *arr4 = SortTestHelper::CreateRandomArray(N, 0, 100);
int *arr5 = SortTestHelper::copyIntArray(arr4, N);
int *arr6 = SortTestHelper::copyIntArray(arr4, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr4, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr5, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr6, N);
cout << endl;

//基本有序
int *arr7 = SortTestHelper::CreateRandomArray(N, 0, 10);
int *arr8 = SortTestHelper::copyIntArray(arr7, N);
int *arr9 = SortTestHelper::copyIntArray(arr7, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr7, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr8, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr9, N);
cout << endl;

delete[] arr1;delete[] arr2;delete[] arr3;delete[] arr4;
delete[] arr5;delete[] arr6;delete[] arr7;delete[] arr8;delete[] arr9;

测试结果：

单路快排优化前：

——–随机数组，随机性大

  • mergeSort : 0.016308s
  • QuickSort : 0.014031s

——–近乎有序

  • mergeSort : 0.010497s
  • QuickSort : 0.126878s

——–基本有序

  • mergeSort : 0.010212s
  • QuickSort : 5.41626s

单路快排优化后：

——–随机数组，随机性大

  • mergeSort : 0.016547s
  • QuickSort : 0.014206s

——–近乎有序

  • mergeSort : 0.010161s
  • QuickSort : 0.008539s

——–基本有序

  • mergeSort : 0.00811s
  • QuickSort : 0.00814s

两种排序算法都是没有优化的，由结果看到，没有优化前归并排序和快速排序在随机性很大时效率差不多，但是在趋向于有序数组的排序时，归并排序效率更高，这是由于归并排序是和旁边比较再来进行交换操作，如果是本来有序，就会减少这一步的操作。但是快排在本身有序时由于是和哨兵比较的，所以会退化为冒泡法(n*n时间复杂度)。 所以在此引出随机快速排序的必要性，随机性的取出一个元素当哨兵，可以大大减小对于本身有序数组退化为冒泡法。

双路快排+优化：

——–随机数组，随机性大

  • mergeSort : 0.015332s
  • QuickSort : 0.012013s

——–近乎有序

  • mergeSort : 0.010009s
  • QuickSort : 0.005201s

——–基本有序

  • mergeSort : 0.008303s
  • QuickSort : 0.005511s

这里测试要注意，修改测试代码为如下：

int N = 100000;

//稀疏数组，随机性大
int *arr1 = SortTestHelper::CreateRandomArray(N, 0, N);
int *arr2 = SortTestHelper::copyIntArray(arr1, N);
int *arr3 = SortTestHelper::copyIntArray(arr1, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr1, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr2, N);
SortTestHelper::testSort("QuickSort3Ways", QuickSortFunc::QuickSort3Ways, arr3, N);
cout << endl;

//近乎有序
int *arr4 = SortTestHelper::CreateNearlyRandomArray(N, 100);
int *arr5 = SortTestHelper::copyIntArray(arr4, N);
int *arr6 = SortTestHelper::copyIntArray(arr4, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr4, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr5, N);
SortTestHelper::testSort("QuickSort3Ways", QuickSortFunc::QuickSort3Ways, arr6, N);
cout << endl;

//大量重复元素
int *arr7 = SortTestHelper::CreateRandomArray(N, 0, 10);
int *arr8 = SortTestHelper::copyIntArray(arr7, N);
int *arr9 = SortTestHelper::copyIntArray(arr7, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr7, N);
SortTestHelper::testSort("QuickSort", QuickSortFunc::QuickSort, arr8, N);
SortTestHelper::testSort("QuickSort3Ways", QuickSortFunc::QuickSort3Ways, arr9, N);
cout << endl;

delete[] arr1;
delete[] arr2;
delete[] arr3;
delete[] arr4;
delete[] arr5;
delete[] arr6;
delete[] arr7;
delete[] arr8;
delete[] arr9;

三路快排+优化：

——–随机数组，随机性大

  • mergeSort : 0.013941s
  • QuickSort2Ways : 0.012005s
  • QuickSort3Ways : 0.016114s

——–近乎有序

  • mergeSort : 0.011044s
  • QuickSort2Ways : 0.005233s
  • QuickSort3Ways : 0.011321s

——–基本有序

  • mergeSort : 0.009525s
  • QuickSort2Ways : 0.006313s
  • QuickSort3Ways : 0.003523s

由结果看到，在数列包含大量的重复元素时，三路快排比双路快排效率高很多。不过在其他随机性大，近似有序情况下，效率就比双路快排低了。所以学习算法应该要明白一个道理：没有最优的算法，只有更优或更适合的算法。每个算法的应用场景不一样。

总结

针对不同的情况使用不同的排序算法：

  • 1.如果是简单对象数据，例如int，double，且数组长度在一定阀值内，则使用快排，如果在阀值外，则用归并
  • 2.如果是复杂对象数组，则如果数组长度在一定阀值以内，则使用折半插入排序，如果长度在阀值外，则使用归并法，但是如果归并二分后小于阀值了，则在内部还是会使用折半插入排序。
CATALOG
    FEATURED TAGS
    生活 品味ZooKeeper 数据挖掘 排序算法 网络编程 golang c++ 并发 网络协议 linux STL 设计模式 Mysql Protobuf mysql go redis docker 加解密 中间件 总结 性能分析 分布式 性能 消息队列