快排的三种实现方式

下面三种算法都是取了一个随机数作为被对比元素。防止在数组是较为有序（比如十万个数中只有数十个乱序的数），的情况下造成分割不平儿，退化成O(n^2)级别的排序。

同时还有别的优化思路，比如在递归到一个比较小级别的数组的时候，插入排序是比快排快的。就可以考虑在(right - left == 15)的情况下，换成插入排序。

单路快排

简单，而且是O(nlogn)级别的快速排序。适合白板写。

在有较多重复元素的时候有，会造成左右分配不平衡的问题，可能会退化成O(n^2)级别的排序。

template <typename T>
void quciSort(T arr[], int l, int r);

template <typename T>
int __quickSort(T arr[], int l, int r);

template <typename T>
void quciSort(T arr[],int n) {
    __quickSort(arr, 0, n-1);
}

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

    if (l >= r)
        return;

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

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

双路快排

最为经典的快排，可以处理绝大部分情况。

template <typename T>
void quickSort2(T arr[], int n);
template <typename T>
void quickSort2(T arr[], int l, int r);

template <typename T>
void quickSort2(T arr[], int n) {
    __quickSort2(arr,0,n-1);
}

template <typename T>
void __quickSort2(T arr[], int l, int r) {
    if (l >= r)
        return;

    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    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]);
    __quickSort2(arr,l,j-1);
    __quickSort2(arr,j+1,r);
}

三路快排

比双路快排多考虑一个与被对比元素相等的情况。在完全随机且left-right较大的情况下，会比双路慢一丢丢（因为多一个判断）。但在有大量相同的元素的情况下，速度很快。

这个看看就行了，我也是抄的。

template <typename T>
void quickSort3Ways(T arr[], int n);

template <typename T>
void __quickSort3Ways(T arr[], int l, int r);

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

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

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

    if( l >= r )
        return;

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