快速排序---真的很快

快速排序（QuickSort）是对冒泡排序(BubbleSort)的一种改进，它们都是基于元素交换的排序方式。与冒泡排序不同，快速排序的每次交换并不一定是相邻元素间的交换，两个元素可能相隔很远，这样就大大减少了总的交换次数。

算法原理

快速排序算法由C. A. R. Hoare在1962年提出。它的基本原理是：每趟排序开始前选定一个主元，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比主元小，并且另外一部分的所有数据都比主元大，这样经过一趟排序就至少可以使一个元素（主元）到达最终位置。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。简单来说，就是每趟排序使本次的主元到达最终位置然后对主元左右两部分再分别排序。

时间复杂度

一般情况下，快速排序的时间复杂度是O(NlogN）的，但是最坏情况下（数据已基本有序）会达到O(N^2)。可以通过画递归树或者是数学归纳的方法来证明，此处不作介绍，具体请参考相关书籍（算法导论等）。

改进（随机化快速排序）

快速排序的执行情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数据已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(N^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(NlogN)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”

随机化快速排序的缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于N个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(N^2)。解决方法是用一种方法进行扫描，使没有交换的情况下主元保留在原位置。另一个缺点是，调用随机函数也会带来时间上的消耗，如果选取不当，那么随机化的意义也就不大。

总的来说，平均情况下快速排序是目前基于关键词比较的排序算法中效率最高的，特别是在大数据的情况下。顺便说一句，当数据很少时，快速排序不是理想算法，这时应采用插入算法。

排序过程演示

下面给出是对某组数据第一趟排序的过程演示（点击以查看大图）。

实例代码

下面是供参考的C++代码：

/*
 * ps：(point start)所需排序的数据首地址
 * pe：(point end) 所需排序的数据第一个无效地址
 * cmp：自定义的比较函数
 */
int sort(int *ps,int *pe,bool(*cmp)(int,int))
{
	if(pe - ps <= 1) //递归出口
		return 0;

	int i = 1;
	int j = pe-ps-1;

	while(true)//这么写主要是考虑交换后还要做一次下面的两个循环
	{
		while(cmp(ps[i],ps[0]) && i<pe-ps-1)
			i++;//从左向右找到第一个比主元大的元素 
		
		while(cmp(ps[0],ps[j]) && j>0)
			j--;//从右向左找到第一个比主元小的元素

		/*
		 * 如果主元最终位置左边有更大的元素，并且右边有更小的元素，则交换它们
		 * swap函数包含在标准库函数中，可以自己写成内联函数以加快速度
		 */ 
		if(i<j)
			swap(ps[i++],ps[j--]);
		/*
		 * 左边找不到更大元素且右边找不到更小元素，说明
		 * 已满足主元最终位置左边都比主元小，右边亦然，则退出循环
		 */
		else 
			break;
	}

		//交换，使得主元到达最终位置
		swap(ps[0],ps[j]);
		sort(ps,ps+j,cmp);   //排主元左边元素
		sort(ps+j+1,pe,cmp); //排主元右边元素
		
		return 0;
}

详细代码请点击这里查看。