Fork me on GitHub

你真的懂快速排序算法吗?

前言

快速排序是互联网公司面试题中出现频率非常高的一道题,通常会要求面试者能够手写出快速排序。今天主要介绍快速排序思想,和3个快速排序的优化,然后引出三路快速排序,最后应用快速排序的思想来解决一道“数列中第k大的数”的算法题。

定义(百度百科)

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

算法步骤(wiki)

  • 从数列中挑出一个元素,称为”基准”(pivot),
  • 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序代码实现(basic)

分析

步骤分析

  • 首先寻找基准元素;
  • 分区(partition):所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面;
  • 递归的对左右两边的子数列进行递归排序

partition图示(初始条件很重要)

partition的某个时刻

初始时刻

  • 当e>=v时, i直接i++

e>=v

  • 当e < v时, arr[j+1] <=> e互换, j++, i++

e < v

  • 最后的状态为:(返回j)

最后的状态

代码实现

最重要的是实现partition函数,而实现partition函数最重要的是初始化状态值(j = l,i=l+1)

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

优化点1

通常面试者写出了上面的快速排序后,面试官一般会问是否有其他的一些优化点。

分析

我们知道当一个数列基本有序的时候,采用直接插入排序算法是非常快的。

解决

我们对上述基本的快速排序进行改进。当数列的大小在小于16的时候直接对数列进行插入排序

代码实现(修改__quickSort函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 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

对于排序数列本身基本有序的情况

当数组近乎有序的情况下,快速排序每次划分的数列极其不平衡,几乎退化成O(N*N)时间复杂度的算法
partition造成数列及其不平衡

有没有解决方法,有的!只要每次随机的选取“基准数“即可。

问题解决(代码实现)

只需要在partition代码中加入rand函数

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
template <typename T>
int _partition(T arr[], int l, int r){
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;
}
```
## 优化点3 (对于数列中有大量重复元素的情况)
### 分析
当数列中存在大量重复元素时,我们会发现快排速度很慢,这时候快速排序又会蜕化成O(n * n)时间复杂度的算法了。在我们的代码中,对于arr[i]等于v的情况都放到了右边,所以会造成partition造成极度不平衡,这也是算法蜕化成O(n * n)时间复杂度的原因:
![partition后极度不平衡](http://fanqietotop.cn/1532250849710lrcxy40z.png?imageslim)
### 数列中存在大量重复元素时的partition分析
* 初始场景
![初始场景](https://note.youdao.com/src/189DA03F1FC0465388F3627870492C74)
* arr[i] < e, 直接i++
![arr[i] < e](http://fanqietotop.cn/1532528606291yauz4p6n.png?imageslim)
* arr[j] > e, 直接j--
![arr[j] > e](http://fanqietotop.cn/15325284610267v7uzyfk.png?imageslim)
* 直到arr[i] == e,arr[j] == e, swap(arr[i],arr[j]);这时候,与v重复的元素就均匀的分布在数列的两边
![arr[i] == e,arr[j] == e](http://fanqietotop.cn/1532528418057sbjilsq5.png?imageslim)
此时就解决了partition时极度不平衡的问题
### 代码实现(修改partition函数)
```c++
//对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p],arr[p]均匀的分散在两边
template <typename T>
int _partition2(T arr[], int l, int r){
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 ){
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]);
return j;
}

三路快速排序算法

定义

三路快速排序是快速排序的的一个优化版本, 将数组分成三段, 即小于基准元素、 等于 基准元素和大于基准元素, 这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。

代码实现

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
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
if( r - l <= 15 ){
insertionSort(arr,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);
}
template <typename T>
void quickSort3Ways(T arr[], int n){
srand(time(NULL));
__quickSort3Ways( arr, 0, n-1);
}

快速排序算法思想的应用

数列中第k大的数(leetcode 215)

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

思路分析

利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:

  • Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
  • Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(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
class Solution {
private:
//对数组nums[l...r]进行快速排序
//在nums[l...r]中寻找第k大的值
int selectK(vector<int>& nums, int l, int r, int k){
if (l == r) {
return nums[l];
}
// 如果 k == p + 1, 直接返回nums[p]
int p = partition(nums, l, r);
if (p + 1== k) {
return nums[p];
}else if(p + 1 > k){
return selectK(nums, l, p-1, k);
}else{
return selectK(nums, p+1, r, k);
}
}
//对nums[l...r]部分进行partition操作
// 返回p,使得nums[l...p-1] > nums[p] ; nums[p+1...r] < nums[p]
int partition(vector<int>& nums, int l, int r){
int v = nums[l];
int p = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( nums[i] > v ){
p ++;
swap( nums[p] , nums[i] );
}
swap( nums[l] , nums[p]);
return p;
}
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
assert(k >= 0 && k <= n);
return selectK(nums, 0, n-1, k);
}
};
-------------本文结束 感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!