快速排序简易入门

快速排序

快速排序(Quick Sort)因其 $O(NlogN)$ 的复杂度成为最常见的算法之一,甚至被纳入了 C++ 的标准库作为 std::sort 的一部分与插入排序糅合在一起以实现更优的时间复杂度。

在学习快速排序算法之前,让我们首先回顾最经典的排序算法——冒泡排序:经过 $(N-1)!$ 次比较,以 $O(N!)$ 的复杂度完成排序。由于冒泡排序每次只比对相邻的两个元素,所以排序效率相对比较低。

快速排序的优势在于,应用了分治的思想(有点像二分),通过多次迭代将元素依次归位,最终完成排序。单元操作如下:

  1. 最左端 选取端元素作为基准数
  2. 使用下标 i 从 最右端 开始寻找小于基准数的元素
  3. 使用下标 j 从 最左端 开始寻找大于基准数的元素
  4. 交换满足条件后的 i, j 下标所对应的元素,然后重复过程 2, 3 直至两下标相遇
  5. 将两下标所处元素与基准数交换

经过以上过程后,基准数左侧的元素均小于等于基准数,基准数右侧的元素均大于等于基准数。接着通过迭代的方式,将此时基准数左端区域与右端区域分别进行下一轮排序操作。当区间内只剩下一个元素时,结束当前过程。

注意:

一、快速排序中扫描时 必须从基准数的对面开始

原因:允许交换的前提:

1. 有 arr[r] < arr[L];

2. 有 arr[l] > arr[L]。

如果从左边开始,则在 l 与 r 相遇时可能只满足了 2 但未满足 1,此时基准数 arr[L] 与 arr[l](arr[r])发生交换,导致一个大于基准数的值被放在了最左。

二、基准数归位后就固定了,接下来分治排列 [L, l – 1] 和 [l+1, R] 即可。(此时 r == l)

改进

对于原始的快速排序,由于每次都从固定的一端选取基准数,当遇到有序序列时,可能会导致基准数归位后其余元素都在基准数的某一侧,而另一侧没有元素的情况,最终导致排序性能退化。为了避免这种情况出现,我们需要引入一个随机化操作来打乱有序序列:在当前区间内随机选取一个元素与基准数交换,然后以其作为新的基准数。示例代码如下:

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
81
82
83
84
85
86
87
88
89
90
#define INF
#define offline
#include "bits/stdc++.h"
using namespace std;

// int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int arr[100010];
int n;
int t;

inline void Swap(int *a, int *b)
{
t = *a;
*a = *b;
*b = t;
}

inline int readint()
{
char c;
bool neg = false;
while((c = getchar()) &lt; '0' || c &gt; '9')
neg = c == '-';//等价于 neg = (c == '-'),因为 == 的优先级更高
int a = c - '0';
while((c = getchar()) &gt;= '0' &amp;&amp; c &lt;= '9')
a = a * 10 + c - '0';
return neg ? -a : a;
}

inline void Out(int n)
{
if (n &lt; 0)
putchar('-'), n = -n;
if (n &gt;= 10)
Out(n / 10);
putchar(n % 10 + '0');
}

inline void quicksort(int L, int R)
{
int l = L;
int r = R;

Swap(&amp;arr[L + ((int)rand() % (R - L))], &amp;arr[L]);
while (l &lt; r)
{
if (arr[r] &lt; arr[L])
{
while (l &lt; r)
{
if (arr[l] &gt; arr[L])
{
Swap(&amp;arr[l], &amp;arr[r]);
break;
}
else
l++;
}
}
r--;
}
Swap(&amp;arr[L], &amp;arr[l]);
if (L &lt; l - 1)
quicksort(L, l - 1);
if (R &gt; r + 1)
quicksort(r + 1, R);
}

int main()
{
//std::ios_base::sync_with_stdio(false);
//std::cin.tie(0);
//srand((unsigned int)(time(NULL)));
// n = 10;
scanf("%d", &amp;n);
for (int i = 0; i &lt; n; ++i)
arr[i] = readint();

quicksort(0, n - 1);

for (int i = 0; i &lt; n - 1; ++i)
{
Out(arr[i]);
putchar(' ');
}
Out(arr[n-1]);
putchar('\n');

return 0;
}