快速排序(Quick Sort) - 算法笔记

妈妈再也不用担心我只会冒泡排序啦~

Posted by ChungZH on 2018-10-13

这篇文章我们来学习快速排序(Quick Sort)

快速排序(Quicksort)是对冒泡排序的一种改进。

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

下面我们用 6 1 2 7 9 3 4 5 10 8 这十个数字来举例说明快速排序的排序过程。

首先,我们需要在这个序列中找到一个基准数。为了方便,我们用 6 作为基准数。接下来,我们要将这个序列中所有比 6 小的数全部放在 6 的左边,把比 6 大的数全部放在它的右边。即成为这个序列:3 1 2 5 4 6 9 7 10 8

然后,我们分别从序列的两端开始“探测”。先从找到一个小于基准数 6 的数,然后再从找到一个大于基准数的数,然后把他们交换即可。这里我们用变量 ij 表示序列的最左边和最右边。我们可以把它们叫做“哨兵i”和“哨兵j”。开始的时候把哨兵i指向序列的第一个数(i=1),即指向 6(注意这里是指向第一个数,不是i等于第一个数) ,然后把哨兵j指向序列的最后一个数(j=n),即指向 8 ,如下图。

QuickSort

首先,哨兵j开始寻找比基准数小的数。哨兵j一步一步向左移动(j–),直到找到了一个小于基准数的数字才停下来。哨兵j移动完后,哨兵i就开始向右移动了,直到找到一个比基准数大的数字。最后,哨兵i停在了数字 7 的位置,哨兵j停在了数字 5 的位置。

然后交换哨兵i和哨兵j指向的元素的值。交换后,序列变成了这样:6 1 2 5 9 3 4 7 10 8。然后哨兵j继续向左移动(每次都是哨兵j先移动),移动到 4(比基准数要小)的时候就停了下来。哨兵i也开始移动了,移动到 9 (比基准数大)的时候,就停了下来。然后再次进行交换,即 49 进行交换。交换后序列就变成这样:6 1 2 5 4 3 9 7 10 8

好了,继续探测。哨兵j继续向左移动,于是它找到了 3 (比基准数小),就停下来了。哨兵i就开始向右移动了。此时,两个哨兵相遇了。两个哨兵都在 3 的位置上,说明探测结束了。把基准数 63 交换就可以了。

交换后的序列如下:3 1 2 5 4 6 9 7 10 8,我们可以发现:在 6 左边的数都小于 6 ,在 6 右边的数全都大于 6 ,至此,我们就完成了第一轮探测。

虽然已经完成了第一轮探测,但是我们可以发现左右两边的数还是凌乱的,并没有按顺序排列。

我们先回顾一下刚才排序的过程:哨兵j找到比基准数小的数,哨兵i找到比基准数大的数,然后进行交换。直到i和j碰头,才和基准数交换。

接下来,我们只需要重复刚才排序的过程,把 6 左边的序列 3 1 2 5 46 右边的序列 9 7 10 8 分别进行快速排序,直到不可拆分出新的子序列为止。最后会得出这个序列:1 2 3 4 5 6 7 8 9 10 。下面上代码。

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
#include <iostream>
#include <algorithm>
using namespace std;
int a[101]; // 由于这个数组需要在函数中使用,所以定义为全局变量
void quicksort(int left, int right); // 定义快速排序函数
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}

quicksort(1, n);

for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}

void quicksort(int left, int right)
{
int i, j;
int temp;
if (left > right)
return;

temp = a[left]; // 基准数
i = left; j = right; // 两个哨兵

while (i != j) // 两个哨兵一碰面就退出循环
{
while (a[j] >= temp && i < j) // 哨兵j 向左寻找比基准数小的数
{
j--;
}
while (a[i] <= temp && i < j) // 哨兵i 向右寻找比基准数大的数
{
i++;
}

// 如果哨兵i和哨兵j还没碰面,就把两个哨兵指向的元素交换。
if (i < j)
{
swap(a[i], a[j]);
}
}

// 最后将哨兵i和基准数交换
a[left]=a[i];
a[i] = temp;

quicksort(left, i-1); // 继续处理左边的(递归)
quicksort(i+1, right); // 继续处理右边的(递归)
return;

}

(代码比桶排序的长多了。。。)

下面我们看运行结果。

输入:

1
2
10
6 1 2 7 9 3 4 5 10 8

输出:

1
1 2 3 4 5 6 7 8 9 10

为了方便理解,我写出程序执行过程中数组a的变化过程给大家看一下。

1
2
3
4
5
6
7
8
9
10
11
6 1 2 7 9 3 4 5 10 8
3 1 2 5 4 6 9 7 10 8
2 1 3 5 4 6 9 7 10 8
1 2 3 5 4 6 9 7 10 8
1 2 3 5 4 6 9 7 10 8
1 2 3 4 5 6 9 7 10 8
1 2 3 4 5 6 9 7 10 8
1 2 3 4 5 6 8 7 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

不难发现,其实快速排序是基于一种叫做“二分”的思想的。大家可以自行了解。

下篇文章我们讲一个需要用到排序的题目。


如果你想学习数据结构和算法,却苦于没有简单易学的教程,那么我给你推荐下面这个课程:

AI前奏必备-数据结构与算法课 - 老九学堂

(此课程中还有Cocos2dx和前端入门课赠送。)


作者:ChungZH

本文大量参考 啊哈磊 所著 《啊哈!算法》。