基础算法之快速排序

发布于   |   分类于   |     |   阅读次数

什么是快速排序

快速排序平均时间复杂度为O(n*logn)，最坏情况(基本有序)下时间复杂度降至O(n^2)，可以通过改进避免

如何实现

交换元素：

1
2
3
4
5
6
//交换元素
void swap(int a[], int i, int j){
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

一般有单边扫描和双边扫描两种实现，双边扫描比单边扫描稍快一些
单边扫描版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//c++实现快速排序_单边扫描版本
void sort(int a[], int low, int high){
    if (low < high) {
        int last = low - 1;
        for (int i = low; i <= high - 1; i++) {
            if (a[i] < a[high]) {
                swap(a, ++last, i);
            }
        }
        swap(a, ++last, high);
        sort(a, low, last - 1);
        sort(a, last + 1, high);
    }
}

双边扫描版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//c++实现快速排序_双边扫描版本
void sort(int a[], int low, int high){
    if (low < high) {
        int i = low - 1;
        int j = high;
        while(true) {
            do{
                i++;
            } while (i <= high - 1 && a[i] < a[high]);
            do{
                j--;
            } while (j >= low && a[j] > a[high]);
            if (i > j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, high);
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
}

然后可以加入基准随机化避免基本有序的情况下复杂度降至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
//c++实现快速排序_双边扫描版本_基准随机化
void sort(int a[], int low, int high){
    if (low < high) {
        int randomIndex = rand() % (high - low + 1) + low;
        swap(a, randomIndex, high);
        int i = low - 1;
        int j = high;
        while(true) {
            do{
                i++;
            } while (i <= high - 1 && a[i] < a[high]);
            do{
                j--;
            } while (j >= low && a[j] > a[high]);
            if (i > j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, high);
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
}

最后可以利用插入排序在基本有序情况下效率很高这一点进一步优化。
双边扫描+基准随机化+利用插入排序优化版本：

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
//c++实现快速排序_双边扫描版本_基准随机化_利用插入排序优化
void insertSort(int a[], int n){
    for (int i = 1; i < n; i++) {
        int t = a[i], j;
        for(j = i; j > 0 && t < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = t;
    }
}
void quickSort(int a[], int low, int high){
    if (high - low < 16) {
        return;
    }
    int randomIndex = rand() % (high - low + 1) + low;
    swap(a, randomIndex, high);
    int i = low - 1;
    int j = high;
    while(true) {
        do{
            i++;
        } while (i <= high - 1 && a[i] < a[high]);
        do{
            j--;
        } while (j >= low && a[j] > a[high]);
        if (i > j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, i, high);
    quickSort(a, low, i - 1);
    quickSort(a, i + 1, high);
}
void quickSort(int a[], int n) {
    quickSort(a, 0, n - 1);
    insertSort(a, n);
}

可以看到，high-low小于一个阈值时就返回，quickSort(a, 0, n - 1)执行完毕后数组是一段一段的，段与段有序，段内无序，再使用插入排序可以很快完成排序