快排杀手
Posted on 11 Jul 2011, tagged sortalgorithm
在学习快排的时候，我们都知道快排的最好和平均时间复杂度都是O(nlogn)，最坏时间复杂度是O(n2)的。虽然其最坏时间复杂度比较高，但是我们也把它称为一个很好的排序的方法，因为从概率上来讲，在大量排序时总的时间是平均的时间，而且由于快排的空间复杂度是O(logn)的（递归时栈的花销），因此是很实用的一种排序方法。
然而有些人就是喜欢较真，就是不喜欢用一个最坏时间复杂度这么高的算法。其实这也是有一定道理的，因为在一些特殊场合，比如发射导弹或者火箭等，也许一组数据多出来一点时间就会造成不可挽回的损失。而且还真的有人给出了这样一个算法来针对任意一个版本的快排来生成一个数组，使这个版本的快排达到时间复杂度接近最坏情况。比如如果每次取基准的时候取第一个，那么就生成一个已排好序的数组，这样时间复杂度会达到最高。这个算法号称对几乎所有版本的快速排序都适用，包括随机快排，但是根据我的分析和测试，应该只是对每次随机函数取的种子相同时，也就是每次排序生成的随机序列相同时才有效。
在说这个算法之前，我们先来复习一下快排是怎么排序的。快速排序每趟排序选出一个元素作为基准，把比它小的放在左边，比它大的放在右边。然后再对其左边和右边的部分分别递归进行这样的操作，当什么时候操作的长度为1时，就是已经排好序的了。最好的情况下，每次都把数组平分为两半，那么只需要进行logn次这样的操作就可以了。但是最坏情况下呢？每次只能分出去一个，那么需要进行n次这样的操作，每次操作需要用的时间是O(n)的，所以时间复杂度是O(n2)。所以我们要是能生成一个数组，让它每次选择基准的时候都选择最坏的情况，就可以使快排的时间复杂度趋向于最大了。我们现在就是要想个办法让每次选择的基准都是最小的。
由于快排所进行的操作只有比较和移动，所以我们可以从这两个方面入手。因为一般排序函数的参数中都会有一个比较函数来判断按什么排序，如void qsort(void *base, size_t nmemb, size_t size,int(*compar)(const void *, const void *))中的compar，这使得我们可以推出相应函数内部的实现，所以我们从比较来入手，看怎样能选择出来对应版本快排的基准。
快排在比较的时候，几乎都是基准和另一个数进行比较的，所以当两个从未比较过的数进行比较的时候，我们可以把其中的一个数当作是基准来处理，将它变成当前的最小值，将另一个变成候选的基准。这样一来会有两种情况：第一、选择的数是基准，选对了，这样很好；第二、选择的数不是基准，但是下次比较的时候还是基准在和另一个数比较，由于我们在前一步已经把真正的基准作为候选了，所以下次再进行比较的时候就可以把它选做基准调成最小的值。这样一来，在划分的时候，最多有一个数是比基准要小的，虽然不是让基准变成最小，但是从渐进时间复杂度上来讲，依然是O(n2)的。
其实上面的选择有一个问题，就是我们说在比较的时候，“几乎”都是基准和另一个数在进行比较。但是像三位取中的一些快排版本当中，在选取基准的时候也是要比较的，所以比较的时候不一定是基准在和另一个数进行比较。然而这个是没有关系的，我们考虑的是渐进时间复杂度，考虑数组趋向于无穷时的趋势，所以只要是选取基准时用的时间是O(1)的，那么操作完之后，小于基准的数字数量也是O(1)的，这样每次划分的结果也是趋向于最坏的。
分析过了应该怎样做了之后，接下来就是动手去做了。这里面用到了一个技巧，就是在很多版本的快排当中，在排序的过程中就在移动元素了。为了防止元素的移动，我们可以新申请一个数组，对这个数组进行操作，但是比较的仍然是原数组，所以就算是移动，也是移动新申请的数组，对将要生成的数组没有什么影响。
由于版权关系，大家可以在这里下载到原文章去看看C语言版本的源代码，这里需要注意的是，由于那篇文章是1999年出版的，当时的qsort函数是用快排实现的，然而现在的qsort已经改为用归并排序实现了（如果数据量不是特别大），所以大家可以用自己写的快排去测试一下，或者找到glibc源代码qsort.c文件中的快排。
下面的图像是我分别用自己写的几个版本的快排和qosrt.c中的快排进行的时间测试。其中黄色曲线是n2的函数，蓝色曲线是n*logn的函数，绿色曲线是快排的运行时间，可以看出，这个算法对于以时间为种子的随机快排是没有作用的。
（1）每次取第一个数为基准
（2）老版本的qsort函数
（3）三者取中版本的快排
（4）随机快排
后记：研究这个算法的时候走了很大的弯路。本来研究东西走点弯路也算正常，但是这回的弯路绕的很是莫名其妙并且让我纠结了好几天，这里和大家说一下：glibc(从1.04版本开始）的qsort函数实现已经不是快排了，已经被归并排序所代替。详见glibc源代码中的NEWS文件：“Mike Haertel (of GNU e?grep and malloc fame) has written a new sorting function which uses the merge sort algorithm, and is said to be significantly faster than the old GNU qsort’ function. Merge sort is now the standard qsort’ function. The new algorithm can require a lot of temporary storage; so, the old sorting function is called when the required storage is not available.”意思是说Mike用merge sort（归并排序）写了一个新的排序函数，据说比qsort快，所以代替了标准的qsort，但是由于它要求的空间比较多，当空间不够的时候就会调用原来的快排。所以Linus那句话还是很经典啊：Read the fucking source code.开源的东西就去看看源代码比什么都好。