排序算法之快速排序

发表于

排序算法之快速排序及其优化

快速排序介绍

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n\^2)次比较，但这种状况并不常见。

快速排序 看图说话

实例分析排序过程

待排数组：

快速排序01

选取数组的第一个元素为基准：5

将小于5的元素放在其左边，大于5的元素放在其右边：

快速排序02

然后不断的对左右两边进行上面的分割，最终为：

快速排序04

注意：我用线将当前的数组的顺序连接了起来，这已经是排序完成了，大家看了下面的分割过程，自己将这个过程用这样的图在纸上或者keynote等画出来，之后，下面的程序是非常好理解的！

分析分割过程

我们来看分割： 定义 v 为基准值；定义 l 为数组的第一个元素的索引；j 为小于基准值的最后一个元素的索引；i 为当前和基准值比较的值的索引，e 为 其值。

数组arr中 [l+1,j] 区间的值都是 小于 v 的,[j+1,i-1] 都是大于 v 的，具体如下图：

快速排序05

1.当 e 小于 v 的时候：
把 j+1 位置的值 和 e 交换：

快速排序06

然后 j ++,i ++,就行了；

2.当 e 大于 v 的时候：

这个就简单了 直接 i ++ 就 O 了；

3.当分割完了之后：

快速排序07

此时，只要将 l 和 j 的位置的值交换一下：

快速排序08

我们已经将数组分割成为:左边小于 v ,右边 大于 v.

关于边界处理，请看后面的程序。

下面是分割的代码：

1
2
3
4
5
6
7
8
9
10
11
12
int __partition(int arr[],int l,int r) {
    int v = arr[l];
    int j = l;
    for (int i = l+1; i <= r; i++) {
        if (arr[i] < v) {
            swap(&arr[j +1], &arr[i]);
            j ++;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

相信，有了前面的图，理解这个程序是很容易的。

快速排序，使用递归的方法是很容易理解的，我们这里也采用递归的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void __quickSort(int 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);
}

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

上面不断的递归分割，直到 l > r 结束递归；你能一步步的看到这里，就可以在纸上，手撸快速排序的代码了。

测试一下

和前面的一样 还是四种测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
**************有序*************
sortname:希尔排序　　	 sorttime: 0.004465s
sortname:归并排序 　　 sorttime: 0.023814s
sortname:快速排序　　	 sorttime: 14.126987s

**************近乎有序*************
sortname:希尔排序　　	 sorttime: 0.015746s
sortname:归并排序 　　 sorttime: 0.031117s
sortname:快速排序　　	 sorttime: 0.896174s

**************随机*************
sortname:希尔排序　　	 sorttime: 0.034790s
sortname:归并排序 　　 sorttime: 0.037268s
sortname:快速排序　　	 sorttime: 0.018142s

**************倒叙*************
sortname:希尔排序　　	 sorttime: 0.010014s
sortname:归并排序 　　 sorttime: 0.024656s
sortname:快速排序　　	 sorttime: 23.304824s

快速排序不是号称最快的排序方法么，可是测试结果说明了一切 😂😂😂

其实我们写的这个并没有经过优化，并且快速排序并非能适应所有的排序场景。

随机化快速排序

首先想一下归并排序是不是和快速排序的方法很相似啊，不同的是归并排序是等分的而快速排序不是的，是根据选择的基值来分的，我们上面选择的是数组的第一个

快速排序09

快速排序10

最差的情况是测试用例中 倒叙的：

快速排序10

我们想的是：每次得取数组中中间的那个数值作为基值，但这样做需要重新遍历一遍数组，耗费了大量的时间。我们可以去个折中的方法，就是随机取数组中的值作为基值，且看程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
int __partition_00(int arr[],int l,int r) {
    swap(&arr[l], &arr[rand()%(r-l+1) + l]);
    int v = arr[l];
    int j = l;
    for (int i = l+1; i <= r; i++) {
        if (arr[i] < v) {
            swap(&arr[j +1], &arr[i]);
            j ++;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

程序中的 swap(&arr[l], &arr[rand()%(r-l+1) + l]); 就是使用 rand() 函数 随机取了值 和 为l索引上的值交换，作为基值，虽然还是有可能 降为 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
**************有序*************
sortname:希尔排序　　	 sorttime: 0.004857s
sortname:归并排序　　	 sorttime: 0.026325s
sortname:快速排序　　	 sorttime: 14.352925s
sortname:快速排序随机	 sorttime: 0.013611s

**************近乎有序*************
sortname:希尔排序　　	 sorttime: 0.012678s
sortname:归并排序　　	 sorttime: 0.025845s
sortname:快速排序　　	 sorttime: 0.632769s
sortname:快速排序随机	 sorttime: 0.013047s

**************随机*************
sortname:希尔排序　　	 sorttime: 0.031845s
sortname:归并排序　　	 sorttime: 0.036922s
sortname:快速排序　　	 sorttime: 0.016712s
sortname:快速排序随机	 sorttime: 0.020723s

**************倒序*************
sortname:希尔排序　　	 sorttime: 0.010177s
sortname:归并排序　　	 sorttime: 0.023441s
sortname:快速排序　　	 sorttime: 23.705080s
sortname:快速排序随机	 sorttime: 0.014164s

我们再看时间，是不是在性能上有不小的提升

双路快速排序

在上面测试的几种用例当中 有大量的重复值 这一项让快速排序慢的不是一点点。那为什么这么慢呢？

我们来看一组测试数据：

1
5, 6, 5, 5, 5, 5, 8, 3, 5, 5

第一次进行分割之后变成：

1
[3]   [5, 5, 5, 5, 5, 8, 6, 5, 5]

相信看到这里大家就明白了，快速排序变成了 O(n^2 ) 了：

快速排序10

在这里介绍一种解决方法：双路快速排序

双路快速排序的分析

我们用两路分别从左右两边进行分割；

  • l:指向选取的 v 在数组的首位；
  • i:从左向右指向下一个要扫描的元素；
  • j:从右向左指向下一个要扫描的元素；

然后进行如下操作：

  1. 从左向右扫描直到 >= v 停止；
  2. 从右向左扫描直到 <= v 停止；
  3. 交换 i 和 j 指向的元素；
  4. i++,j++；
  5. 直到 j <= i 停止扫描；

大家可能会有这样的一个疑问：当 左右的两个 e 元素 相等时也会进行交换的

是的，这样可以确保在一定程度上分割平衡。所以分割实际上是这样的：

arr[l+1,i-1] <= v 和 arr[j,r] >= v

双路快速排序的程序代码

现在分割函数写成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int __partition_twoWays(int arr[],int l,int r) {
    swap(&arr[l], &arr[rand()%(r-l+1) + l]);
    int v = arr[l];
    int i = l + 1;
    int j = r;
    while (1) {
        while (i <= r && arr[i] < v) { i ++; }
        while (j >= l+1 && arr[j] > v) { j --; }
        if (j <= i) { break; }
        swap(&arr[i], &arr[j]);
        i++;
        j--;
    }
    swap(&arr[l], &arr[j]);
    return j;
}

测试

我们再来看测试(测试用例 50w个)：

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
**************有序*************
sortname:插入排序优化	 sorttime: 0.002745s
sortname:希尔排序　　	 sorttime: 0.026173s
sortname:快速排序随机	 sorttime: 0.078291s
sortname:快速排序双路	 sorttime: 0.047122s

**************近乎有序*************
sortname:插入排序优化	 sorttime: 0.010042s
sortname:希尔排序　　	 sorttime: 0.030206s
sortname:快速排序随机	 sorttime: 0.063545s
sortname:快速排序双路	 sorttime: 0.046858s

**************有大量的重复值*************
sortname:希尔排序　　	 sorttime: 0.053225s
sortname:快速排序随机	 sorttime: 27.211613s
sortname:快速排序双路	 sorttime: 0.058205s

**************随机*************
sortname:希尔排序　　	 sorttime: 0.179634s
sortname:快速排序随机	 sorttime: 0.102915s
sortname:快速排序双路	 sorttime: 0.102822s

**************倒叙*************
sortname:希尔排序　　	 sorttime: 0.056003s
sortname:快速排序随机	 sorttime: 0.065304s
sortname:快速排序双路	 sorttime: 0.048225s

我们可以看到 双路快速排序 的时间相比之前快了不少！

三路快速排序

关于 有大量的重复值 的快速排序还有一种经典的解法 -> 三路快速排序

三路快速排序的分析

我们重新定义了如下几个变量：

  • l:指向选取的 v 在数组的首位；
  • lt:从左向右 小于v 的最后一个元素(初始情况: lt = l)；
  • i:从左向右指向下一个要扫描的元素(初始情况: i = l + 1)；
  • gt:从右向左 大于v 的第一个元素（初始情况: gt = r + 1）；

初始的情况

当 e == v 时

这个很简单 直接 i ++ 就行了，如下图

然后：

当 e < v 时

将 i 指向的元素 和 lt+1 指向的元素 交换位置，然后 i++ , lt++

然后：

当 e > v 时

将 i 指向的元素 和 gt-1 指向的元素 交换位置，然后 gt –

然后：

扫描完成时

三路快速排序的程序代码

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
void __quickSort_threeWays(int arr[],int l,int r) {
    if (l >= r) {
        return;
    }
    swap(&arr[l], &arr[rand()%(r-l+1) + l]);
    int v = arr[l];
    // arr[l+1...lt] < v 、 arr[lt+1...i-1] == v 和 arr[gt...r] > v
    int lt = l;
    int i  = l + 1;
    int gt = r + 1;
    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 {
            i ++;
        }
    }
    swap(&arr[l], &arr[lt]);
    __quickSort_threeWays(arr, l, lt-1);
    __quickSort_threeWays(arr, gt, r);
}

void quickSort_threeWays(int arr[],int n) {
    srand((unsigned)time(NULL));
    __quickSort_threeWays(arr,0,n-1);
}

测试

我们再来看测试(测试用例 50w个)：

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
**************有序*************
sortname:插入排序优化	 sorttime: 0.003101s
sortname:希尔排序　　	 sorttime: 0.023716s
sortname:快速排序随机	 sorttime: 0.070738s
sortname:快速排序双路	 sorttime: 0.057771s
sortname:快速排序三路	 sorttime: 0.110716s

**************近乎有序*************
sortname:插入排序优化	 sorttime: 0.014255s
sortname:希尔排序　　	 sorttime: 0.033605s
sortname:快速排序随机	 sorttime: 0.067371s
sortname:快速排序双路	 sorttime: 0.051204s
sortname:快速排序三路	 sorttime: 0.106871s

**************有大量的重复值*************
sortname:希尔排序　　	 sorttime: 0.054126s
sortname:快速排序随机	 sorttime: 27.016716s
sortname:快速排序双路	 sorttime: 0.054265s
sortname:快速排序三路	 sorttime: 0.014668s

**************随机*************
sortname:希尔排序　　	 sorttime: 0.175923s
sortname:快速排序随机	 sorttime: 0.099126s
sortname:快速排序双路	 sorttime: 0.098717s
sortname:快速排序三路	 sorttime: 0.111747s

**************倒叙*************
sortname:希尔排序　　	 sorttime: 0.059569s
sortname:快速排序随机	 sorttime: 0.065489s
sortname:快速排序双路	 sorttime: 0.047557s
sortname:快速排序三路	 sorttime: 0.090296s

我们可以看到对 有大量的重复值 排序又快了一点点。当然在其它情况下，三路快速排序的时间都很稳定，所以三路快速排序应当是首选。

结束

至此，快速排序便介绍完了，后面即将介绍 堆排序。

最后附上Demo