nlog(n)级别排序二 快速排序

快速排序原理

快速排序是另一个时间复杂度在nlog(n)级别的排序算法，它的基本思想是这样的：每次找出一个元素，把这个元素放到它有序时应该在的位置，操作完成后，再把该元素左边的元素和右边的元素进行同样的操作，直至整个数组排序完成。因此，在快速排序当中也适用了递归的方法。下面给出它的基础实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//
// Created by madman on 2017/7/25.
// 快速排序
//

#include "iostream"
using namespace std;

//对arr [l,r]区间进行partition操作，找出一个元素应该在的位置
int __partition(int arr[], int l, int r){
    //要确定位置的元素，默认选择第一个
    int v = arr[l];
    //元素v排好序后应该在的位置
    int j = l;
    //从v后面一次考察每一个元素
    for(int i=l+1;i<=r;i++){
        if(arr[i]<v){
            swap(arr[i], arr[j+1]);
            j++;
        }
    }
    //考察完毕，找到v应该在的位置，进行交换，并返回找到的位置
    swap(arr[j], arr[l]);
    return j;

}

//对arr中[l,r]区间进行快速排序
void __quickSort(int arr[], int l, int r){
    if(l>=r)return;
    //得到当前操作确定的位置，对该位置两边再次进行partition操作
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);

}

void quickSort(int arr[], int n){
    __quickSort(arr, 0, n-1);
}

int main(){
    int arr[] = {4,1,3,6,7,2,8,22,12,15,21,9,42,90};
    //int arr[] = {4,1,3,6,1,2,2,22,3,15,21,9,42,90};
    quickSort(arr, 14);
    for(int i=0;i<14;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

partition操作解释

其整个过程与归并排序操作类似，最核心的地方在于__partition方法，它完成了上面所说的，选择一个元素并把它放到应该在的位置上，同时返回了该位置，以便递归的进行。在整个过程中，设置了3个变量，v表示被选中的元素，它将被放到正确的位置，j指向v应该在的位置，i则进行整个数组的遍历。在这个过程中，v默认选择了第一个元素，在后面的遍历中，依次考察了v后面的每一个元素，j初始位置指向v，在整个过程中，要保证arr[l+1,j]<v,arr[j+1,r]>v。在考察arr[i]与v的关系时，如果arr[i]<v，表明该元素应该在v的左边，把这个元素交换过来，相当于扩充了arr[l+1,j]当中的元素，因此j++,如果arr[i]>v则它就应该在右侧，此时只需要继续考察下一个元素即可。

直到上述过程完成，j指向了元素v的位置，因此将两个位置的元素交换，就把v放到了正确的位置上。__quickSort方法则对划分出来的两部分继续递归，直至完成。这便是快速排序的基础实现。但该实现有一些缺陷存在，并会导致在某些情况下复杂度的退化，因此有一些优化的方法，后面来补充。

优化1

  1. 第一点优化与归并排序一样，在数组划分到一定大小的时候，可以对这一部分进行快速排序，不再继续递归。
  2. 第二点，由于上述快速排序对于元素的选择默认使用了第一个元素，在每次确定位置之后，将数组分为两部分再分别进行排序。与归并排序不同的是，归并排序将数组一分为二，因此可以保证在不断的划分过程中，这棵树的高度是确定的。但快速排序由于选择的元素最后确定的位置并非确定，如果一个近乎有序的数组，将导致数组被分为差异很大的两部分进行排序。在最坏的情况下，一个数组已经有序，此时该结构缺少左子树，退化为一个链表结构，树的高度变为n，此时的复杂度退化为O(n^2)级别。这会导致快速排序的性能急剧下降。

基于上述分析，对于元素的选择，我们可以换一种方式，采用随机的选择，选择数组中的一个元素，这使得数组划分不平衡的概率大大降低，提高速度，下面是其简单的改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//对arr [l,r]区间进行partition操作，找出一个元素应该在的位置
int __partition(int arr[], int l, int r){
    //操作之前随机选择一个元素
    swap(arr[rand()%(r-l+1)+l],arr[l]);
    //要确定位置的元素，此时被替换为一个随机选择的元素
    int v = arr[l];
    //元素v排好序后应该在的位置
    int j = l;
    //从v后面一次考察每一个元素
    for(int i=l+1;i<=r;i++){
        if(arr[i]<v){
            swap(arr[i], arr[j+1]);
            j++;
        }
    }
    //考察完毕，找到v应该在的位置，进行交换，并返回找到的位置
    swap(arr[j], arr[l]);
    return j;

}

//对arr中[l,r]区间进行快速排序
void __quickSort(int arr[], int l, int r){
    // if(l>=r)return;
    //较小部分是采用插入排序进行优化
    if(r-l<=15){
        insertionSort(arr, l, r);
        return;
    }
    //得到当前操作确定的位置，对该位置两边再次进行partition操作
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);

}

优化2，双路快速排序

随机化的选择解决了近乎有序的数组的效率问题，下面考虑一个拥有大量重复值的数组。通过上述的排序过程可知，在选定一个元素后，比该元素小的都放到了左边，则意味着右边所有元素都大于等于该元素。如果出现了一个数组中有大量重复元素，则右边就拥有大量元素，即再次产生了数组不平衡的问题。解决思路是，由原来的单向循环改为前后双向循环。设选定元素为v，则大于v的放到右边，小于v的放到左边。设定由前往后的下标为i,由后往前下标为j,若满足前面的条件，则i、j继续往前/后考察，在不满足时，交换元素，再继续向前考察。

由前面设定的条件可以看出，当arr[i]=v或arr[j]=v时，也会发生交换，这样就把相同的元素都分散到了前后两个部分，以此解决前面出现的不平衡问题。这里变化的是partition过程，下面给出具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//双路快速排序
int __partition2(int arr[], int l, int r){
    swap(arr[rand()%(r-l+1)+l],arr[l]);
    int 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--;
    }
    //j查找的是大于v的元素，它最后的位置应该是最后一个小于等于v的位置，因此和j交换
    swap(arr[l], arr[j]);
    return j;
}

优化3，三路快速排序

经过前面的优化处理，基本上对所出现的特殊情况进行了优化。三路快速排序则对双路进行优化。从双路排序的思想中可以看到，为了平衡数组两部分，对于等于选定点v的值都进行了一次交换，但实际上，对于相同元素较多的时候，等于v这一区间也是非常大的，因此可以将数组划分为3个部分，大于v,等于v,小于v。

在这里设定三个值，lt, gt, i,i为当前考察的元素，lt,gt分别是数组满足arr[l,lt]<v, arr[lt+1,i)=v, arr[gt,r]>v。这样，就避免了对多个重复元素的交换操作，下面看一下实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**三路快速排序**/

void __quickSort3(int arr[], int l, int r){

    if(r-l<=15){
        insertionSort(arr,l,r);
        return;
    }
    //获得arr[l,r]之间随机一个值
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    int v = arr[l];

    //三部分索引
    /**
     * arr[l,lt]<v
     * arr[lt+1,i) = v
     * arr[gt, r] > v
     */
    int lt = l, gt = r+1, i = l+1;
    while(i < gt){
        if(arr[i]< v){
            swap(arr[i], arr[lt+1]);
            lt++;
            i++;
        } else if( arr[i] > v){
            //由于i处被交换来一个新的值，所以i不++，继续考察该元素  
            swap(arr[i], arr[gt-1]);
            gt--;
        } else {
            i++;
        }
    }
    swap(arr[lt], arr[l]);
    //分别在对大于v和小于v的两部分进行排序
    __quickSort3(arr, l, lt-1);
    __quickSort3(arr, gt, r);

}

void quickSort3(int arr[], int n){
    srand(time(NULL));
    __quickSort3(arr, 0, n-1);
}

由于数组被分为3部分，在递归时将会有两个下标，因此没有将partition操作独立出来。上面需要注意lt, i, gt的初始值，由于arr[l,lt]<v,在每次找到小于v的元素的时候都放到这一部分，也就是lt+1的位置，因此初始值为l保证了第一个小于v的元素会放到arr[l]后面一位；i是需要考察的元素，因此初始从l+1开始；gt指向第一个大于v的元素，由于它是从后往前考察，因此满足条件时，arr[gt,r]这部分会扩充，也就是gt--,所以gt=r+1满足了第一个大于v的元素放到了最后一个位置。