这篇文章我们来学习快速排序(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 。下面上代码。

#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;
	
}

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

下面我们看运行结果。

输入:

10
6 1 2 7 9 3 4 5 10 8

输出:

1 2 3 4 5 6 7 8 9 10

为了方便理解,这里给出程序执行过程中数组 a 的变化过程。

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