【C++】快速排序 QuickSort的实现及其两种优化方法-双路快速排序法、三路快速排序法_快速排序cpp

一，第一种实现方法 - 基本法（递归）

（1）基本思路

如下面数组：

 

将第一个元素4移动到中间，在4的左边为小于4的元素，在4的右边为大于4的元素：

（2）基本实现思路

我们进行一个分区（分部）操作：

 

 

 

 

①当e> v，则i ++：

 

 

②当e <v，则

             j ++;
            交换（arr [j]，arr [i]）;

 

 

然后我++，进行下一步 

直到i> n - 1，遍历数组结束：

 

 ③最后，交换（arr [l]，arr [j]）;

（3）完整的实现代码：

 
// 对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];
 
    int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
 
    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);
}

（4）上面的方法有两种优化方法：

①优化方法1：对于小规模数组，使用插入排序进行优化

当元素个数小于16时，我们调用插入排序，

即

 
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

完整代码：

// 对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){
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
 
    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
 
    swap( arr[l] , arr[j]);
 
    return j;
}
 
// 对arr[l...r]部分进行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(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){
 
    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

插入排序代码：

#include <iostream>
#include <algorithm>
 
using namespace std;
 
 
template<typename T>
void insertionSort(T arr[], int n){
 
    for( int i = 1 ; i < n ; 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;
    }
 
    return;
}
 
// 对arr[l...r]范围的数组进行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r){
 
    for( int i = l+1 ; i <= r ; i ++ ) {
 
        T e = arr[i];
        int j;
        for (j = i; j > l && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
 
    return;
}

 

②优化方法2：随机化快速排序法

对于归并排序，每次进行分区操作都是对半分配：

对于快速排序，我们都是去第一个元素为中间值，这个值可能是最小值或最大值或任意大小值，导致分区操作分配不均：

 

当第一个元素为最小值时，出现快速排序最差的情况，变成了一个链表：

所以，我们应该在数组中随机选择一个数而非取第一个数，即随机在arr [l ... r]的范围中，选择一个数值作为标定点pivot：

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

完整的实现代码：

// 对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){
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
 
    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
 
    swap( arr[l] , arr[j]);
 
    return j;
}
 
// 对arr[l...r]部分进行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(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){
 
    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

二，第二种实现方法 - 双路快速排序法

（1）回顾前面第一种方法的分区，在标定元素的两边的元素个数及其不平衡：

（2）所以，我们使用两个指针，同时判断：

       ①while（i <= r && arr [i] <v）
            i ++; 

直到e> = v时，停止：

 

②while（j> = l + 1 && arr [j]> v）
            j - ;

 

直到e <= v时停止：

 

 

 

 

（3）完整的实现代码：
 

// 双路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition2(T arr[], int l, int r){
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    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 ){
        // 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
 
        while( i <= r && arr[i] < v )
            i ++;
 
        // 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
 
        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;
}
 
// 对arr[l...r]部分进行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
 
    // 调用双路快速排序的partition
    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);
}

三，第三种实现方法 - 三路快速排序法

 （1）基本思路

将数组分成三个部分：大于标定点V，等于标定点V，小于标定点五：

小于标定点V在区间arr [l + 1 ... lt]：

大于标定点V在区间arr [gt ... r]：

等于标定点V在区间arr [lt + 1 ... i-1]：

遍历游标我：

①当e = v，i ++;

 

 

 ②当e <v，swap（arr [i]，arr [lt + 1]）

然后，

          i ++;
           lt ++; 

 ③当e> v：
swap（arr [i]，arr [gt-1]）;

 

 

 然后，gt - ;

当我<gt，完成遍历：

 

 

最后，交换（arr [l]，arr [lt]）;

 

 

（2）三路快速排序代码实现：

// 递归的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );
 
    T v = arr[l];
 
    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            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);
}

 四，测试用例

我们用一个n = 1000000个元素的随机数组，测试归并派速，二路快速排序和三路快速排序的所用的时间：yi

①main.cpp

#include <iostream>
#include <algorithm>
#include <ctime>
#include "SortTestHelper.h"
#include "MergeSort.h"
#include "InsertionSort.h"
#include "QuickSort.h"
 
using namespace std;
 
 
// 递归的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序进行优化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );
 
    T v = arr[l];
 
    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            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);
}
 
 
// 比较Merge Sort和双路快速排序和三路快排三种排序算法的性能效率
// 对于包含有大量重复数据的数组, 三路快排有巨大的优势
// 对于一般性的随机数组和近乎有序的数组, 三路快排的效率虽然不是最优的, 但是是在非常可以接受的范围里
// 因此, 在一些语言中, 三路快排是默认的语言库函数中使用的排序算法。比如Java:)
int main() {
 
    int n = 1000000;
 
    // 测试1 一般性测试
    cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
    int* arr1 = SortTestHelper::generateRandomArray(n,0,n);
    int* arr2 = SortTestHelper::copyIntArray(arr1,n);
    int* arr3 = SortTestHelper::copyIntArray(arr1,n);
 
    SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n);
    SortTestHelper::testSort("Quick Sort", quickSort, arr2, n);
    SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n);
 
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
 
    cout<<endl;
 
 
    // 测试2 测试近乎有序的数组
    int swapTimes = 100;
    cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
    arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, n);
    arr3 = SortTestHelper::copyIntArray(arr1, n);
 
    SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n);
    SortTestHelper::testSort("Quick Sort", quickSort, arr2, n);
    SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n);
 
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
 
    cout<<endl;
 
 
    // 测试3 测试存在包含大量相同元素的数组
    cout<<"Test for random array, size = "<<n<<", random range [0,10]"<<endl;
    arr1 = SortTestHelper::generateRandomArray(n,0,10);
    arr2 = SortTestHelper::copyIntArray(arr1, n);
    arr3 = SortTestHelper::copyIntArray(arr1, n);
 
    SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n);
    SortTestHelper::testSort("Quick Sort", quickSort, arr2, n);
    SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n);
 
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
 
 
    return 0;
}

②InsertionSort.h

//
// Created by liuyubobobo on 7/23/16.
//
 
#ifndef INC_08_QUICK_SORT_THREE_WAYS_INSERTIONSORT_H
#define INC_08_QUICK_SORT_THREE_WAYS_INSERTIONSORT_H
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
 
template<typename T>
void insertionSort(T arr[], int n){
 
    for( int i = 1 ; i < n ; 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;
    }
 
    return;
}
 
// 对arr[l...r]范围的数组进行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r){
 
    for( int i = l+1 ; i <= r ; i ++ ) {
 
        T e = arr[i];
        int j;
        for (j = i; j > l && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
 
    return;
}
 
#endif //INC_08_QUICK_SORT_THREE_WAYS_INSERTIONSORT_H

 

③MergeSort.h

//
// Created by liuyubobobo on 7/23/16.
//
 
#ifndef INC_08_QUICK_SORT_THREE_WAYS_MERGESORT_H
#define INC_08_QUICK_SORT_THREE_WAYS_MERGESORT_H
 
#include <iostream>
#include <algorithm>
#include "InsertionSort.h"
 
using namespace std;
 
 
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename  T>
void __merge(T arr[], int l, int mid, int r){
 
    //* VS不支持动态长度数组, 即不能使用 T aux[r-l+1]的方式申请aux的空间
    //* 使用VS的同学, 请使用new的方式申请aux空间
    //* 使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间:)
    T aux[r-l+1];
    //T *aux = new T[r-l+1];
 
    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];
 
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){
 
        if( i > mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }
 
    //delete[] aux;
}
 
// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
 
    // 对于小规模数组, 使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }
 
    int mid = (l+r)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
 
    // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
    // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}
 
template<typename T>
void mergeSort(T arr[], int n){
 
    __mergeSort( arr , 0 , n-1 );
}
 
#endif //INC_08_QUICK_SORT_THREE_WAYS_MERGESORT_H

④QuickSort.h

//
// Created by liuyubobobo on 7/23/16.
//
 
#ifndef INC_07_QUICK_SORT_THREE_WAYS_QUICKSORT_H
#define INC_07_QUICK_SORT_THREE_WAYS_QUICKSORT_H
 
#include <iostream>
#include <ctime>
#include <algorithm>
#include "InsertionSort.h"
 
using namespace std;
 
 
// 对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){
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
 
    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
 
    swap( arr[l] , arr[j]);
 
    return j;
}
 
// 双路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition2(T arr[], int l, int r){
 
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    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 ){
        // 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
        // 思考一下为什么?
        while( i <= r && arr[i] < v )
            i ++;
 
        // 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
        // 思考一下为什么?
        while( j >= l+1 && arr[j] > v )
            j --;
 
        // 对于上面的两个边界的设定, 有的同学在课程的问答区有很好的回答:)
        // 大家可以参考: http://coding.imooc.com/learn/questiondetail/4920.html
 
        if( i > j )
            break;
 
        swap( arr[i] , arr[j] );
        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 <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
 
    // 调用双路快速排序的partition
    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);
}
 
#endif //INC_07_QUICK_SORT_THREE_WAYS_QUICKSORT_H

⑤SortTestHelper.h

//
// Created by liuyubobobo on 7/21/16.
//
 
#ifndef INC_08_QUICK_SORT_THREE_WAYS_SORTTESTHELPER_H
#define INC_08_QUICK_SORT_THREE_WAYS_SORTTESTHELPER_H
 
#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cassert>
 
using namespace std;
 
 
namespace SortTestHelper {
 
    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    int *generateRandomArray(int n, int range_l, int range_r) {
 
        int *arr = new int[n];
 
        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (range_r - range_l + 1) + range_l;
        return arr;
    }
 
    // 生成一个近乎有序的数组
    // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
    // swapTimes定义了数组的无序程度
    int *generateNearlyOrderedArray(int n, int swapTimes){
 
        int *arr = new int[n];
        for(int i = 0 ; i < n ; i ++ )
            arr[i] = i;
 
        srand(time(NULL));
        for( int i = 0 ; i < swapTimes ; i ++ ){
            int posx = rand()%n;
            int posy = rand()%n;
            swap( arr[posx] , arr[posy] );
        }
 
        return arr;
    }
 
    // 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
    int *copyIntArray(int a[], int n){
 
        int *arr = new int[n];
        //* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:)
        copy(a, a+n, arr);
        return arr;
    }
 
    // 打印arr数组的所有内容
    template<typename T>
    void printArray(T arr[], int n) {
 
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
 
        return;
    }
 
    // 判断arr数组是否有序
    template<typename T>
    bool isSorted(T arr[], int n) {
 
        for (int i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                return false;
 
        return true;
    }
 
    // 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
    template<typename T>
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
 
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
 
        assert(isSorted(arr, n));
 
        return;
    }
 
};
 
#endif //INC_08_QUICK_SORT_THREE_WAYS_SORTTESTHELPER_H

 

<本文完>

 

参考资料：

http://coding.imooc.com/class/chapter/71.html#Anchor