快排时间复杂度退化到 O(n²) 的问题

算法书上都会讲：在输入已经有序等特定情况下，快速排序 (quicksort) (最简单的实现) 的时间复杂度会退化到 O(n²)。书上通常建议用 “随机化” 或 “三取中” 的方法选 pivot，并声称这样的算法这样对于非故意构造的真实数据，基本上总是会有一个满意的 O(nlogn) 运行时间。

可惜，事情没这么简单。

不需要故意构造，只要用一个常量数组 (不是常量也行，只要数组中包括比较多的相等元素，比如仅由很小的正整数组成的较长的数组)，不算 pivot 怎么选，大部分教材上的实现都照样退化至 O(n²)。

问题不难发现：这时的问题不在 pivot 的选择，而在 partition 这一步，多数教材上的 partition 代码在区间中有大量元素与 pivot 相等时都会把这些元素分到 pivot 的同一边。

要改进也不难，以《算法导论》上的 partition 代码为例 (比多数国内教材中所用的版本简洁)，改进前：

	while (q != hi) {
		// Loop invariant: *[lo ... p) <= pivot <= *[p, q)
		if (*q < pivot)
			std::swap(*p++, *q);
		++q;
	}

改进后：

	while (q != hi) {
		if (*q < pivot)
			std::swap(*p++, *q);
		++q;

		if (q == hi)
			break;
		if (*q <= pivot)
			std::swap(*p++, *q);
		++q;
	}

其实就是把 “小于” 的判断改成 “小于” 与 “小于等于” 交替，这样与 pivot 相等的元素会被大致平均地分到 pivot 两边。

之所以写这篇博文，就是因为昨天实际碰到了这个问题——对一组真实数据，我自己写的快排 (使用 “三取中” 法选 pivot) 花的时间是 std::sort 的十万倍。做上述改进后即变回到与 std::sort 相当。

这样的改进只是减少了对现实中的真实数据退化的可能性，仍然可以故意构造出 O(n²) 的情况。有更好 (也更复杂) 的解决方案，比如 SGI STL 中用的 introsort，它是一种快速排序与堆排序 (heapsort) 的混合算法，对真实数据的速度与 quicksort 相似，同时最坏情况下的时间复杂度为 O(nlogn)。

标签: coding