前言之前在本BLOG写过一篇快速排序算法普及教程，很多网友反映这篇文章通俗易懂。不过后来有网友algorithm__指出，“quicksort算法是怎么一步一步想到列的？这就像一个P和NP问题，知道了就不难证明了。但是在你知道之前解法，要一点一点，一步一步推导，有这么难吗？其实这个问题我也想过很多次，之前在博客里也提到过很多次了。那么，为什么最后很多人看了我写的快速排序算法，过了一段时间，就没有了知道什么是快速排序吗？”很大一部分原因是只知道表，不知道其中，只知道它的用途，不知道它的本质。很多东西都可以从本质上看出来。但大多数人并没有这样做。所以他们读了就忘了，又忘了再读。就这样，在知识的一次次重复记忆中，始终没有分析出本质，从而形成了恶性循环。因此，归根结底，要学一个东西，不仅要运用自如，还要熟悉它的原理、来龙去脉、精髓。就像侯捷先生说的，只知道一个东西的用法而不知道它的原理是不明智的。你提的问题很好。我会再写一篇文章来彻底解释快速排序算法是如何设计的，以及如何一步步来的。来龙去脉，了解其内部原理。本文着重分析了快速排序算法的流程来源和时间复杂度。1.快速排序的原始版本快速排序的算法思想（此时，它不叫快速排序）最初是由一个叫C.A.R.Hoare的人提出的，他给出了算法思想描述的具体版本，如下：HOARE-PARTITION(A,p,r)x←A[p]i←p-1j←r+1whileTRUEdorepeatj←j-1untilA[j]≤xrepeati←i+1untilA[i]≥xifi”表示赋值）：j（找小），从右到左，连续--直到遇到第一个比key小的元素kj，ki<-kj。i（找大），从左到右，一直++，直到遇到第一个比key大的元素ki，kj<-ki。三、按照上述方法不断进行，直到i和j相遇，ki=key，完成第一次排序，然后重复步骤II，递归进行。当过程HOARE-PARTITION结束时，A[p..j]中的每个元素（这里在算法导论中文版第二版中有打印错误，打印为A[p..r]）小于或等于A[j+1..r]的每个元素。HOARE-PARTITION不同于下面描述的标准PARTITION分区方法。HOARE-PARTITION总是将主元值放入A[p..j]和A[j+1..r]中间的两个分区之一。因为p<（i从左向右移动，向右移动，找到比第一个元素大的那个）通过比较ki和k1，如果Ri经过除法最终会成为左边子序列的一部分，然后是i++，继续i++，直到遇到一个属于右边的子序列Ri（较大）。<--j（j从右向左，向左移动，寻找比第一个元素小的）同理，j--，直到遇到一个更小的应该属于左边子序列的元素Rj（更小）为止，当i<-j（找小）28713564j指的是元素4，大于2，所以j--,i<--j28713564在这个过程中，如果j没有遇到小于2的元素，那么j就会继续--直到j指向1，ij28713564此时，8和1互换，ij21783564此时i指向的元素为1，比2小，所以i不动，j继续--永远不会遇到元素小于2，最后停在7处。ij21783564***，将i指向的元素1与序列中的第一个元素k1交换，即2，i[1]2[783564]这样，2就是把整个序列分成两部分，然后对剩下的待排序数递归进行第二次和第三次排序....从上面的过程，我们可以大致看出这个算法的笨拙。比如上面第一步，当j没有找到小于2的元素时，就需要不断往前走，j--。第二，当交换i指向的元素时，不能保证此时i指向的元素一定小于2，即i指针，有可能继续留在原地，不能被交换感动。一直这样下去，势必会耗费不少时间。后来，更进一步，由于排序速度更快，塞奇威克将其称为“快速排序”，快速排序就这样诞生了。并最终一举成名，成为二十世纪最伟大的10大算法之一。OK，接下来我们看一下Hoare的变体算法。如下，对序列38712564进行排序：1,j--，直到遇到序列中第一个小于键值3的元素2，将2赋值给ki，j指向空元素。ij38712564ij=>28715642.i++指向8，将8重置为j指向的元素的空白处，i指向的元素再次为空：ij2871564ij=>27185643.继续j--遇到1还是小于3（预先保存的键值），指向的空白处赋1tobyi:ij2718564=>21785644.同理，i继续++，遇到7，比key大，7赋给空白j指向的空间。在那之后，我和j相遇了。***pass结束：ij2178564ij=>21785645.***，提前保存的key，即3赋值给ki，也就是i指向的空格，我们得到：[21]3[78564]所以整个行程是这样的：387125642871356423718564217385642137856421378564后续补充：如果要排序的序列是逆序？ok，为了清楚起见，再举个例子，对于序列987654321排序：987654321//9是主成分18765432//j从右到左找小的，找到1，赋值给***18765432//i从左到右找大的，直到遇到才找到j187654329//***,填9。如上，当数组已经是倒序排列时，我们很容易知道，此时数组排序需要O(N^2)时间复杂度。后面会详细分析快速排序的时间复杂度。***，写一个程序来实现这个算法，如下，我相信，我不需要解释太多：intpartition(intdata[],intlo,inthi)//quotedfromwhatever。{intkey=data[lo];intl=lo;inth=hi;while(lr[0]=tab->r[i];//这次准备按照最左边元素的值划分，先保存它的值do{while(tab->r[j].key>tab->r[0].key&&ir[i].key=tab->r[j].key;i++;}//将第j个元素放到左边，并重置iwhile(tab->r[i].keyr[0].key&&ir[j].key=tab->r[我]。key;j--;}//将第i个元素放在右边并重置j}while(i!=j);tab->r[i]=tab->r[0];//设置标准值放在它的最终位置，本次除法结束quicksort(tab,left,i-1);//在标准值的左半部分递归调用此函数quicksort(tab,i+1,right);//对于标准值的右半部分递归调用这个函数}}我想，到此为止，已经解释得够多了。如果还是不明白，那好，伸出手指头数数……好吧，再问各位读者一个问题：像这样从左往右找i，找到第一个比key大的如果是大（设置数组第一个元素为key），kj会被重置，j会从右到左找最小的元素，如果找到第一个比key小的元素，ki会被重置。当然，在这个过程中，i，j是不断变化的，通过++，或者--，指向不同的元素。你有没有想过现实生活中有哪些情况与这种快速排序算法的思想相似？好吧，等你想到了再告诉我也不迟。：D。四、快速排序的优化版本后来N.Lomuto提出了一个新版本，也就是快速排序算法中描述的第一个版本，优化了PARTITION程序，现在写在IntroductiontoAlgorithms一书中，关键到快速排序算法的是PARTITION过程，它将A[p..r]重新排列到位：PARTITION(A,p,r)x←A[r]//with***一个元素，A[r]是主元素i←p-1forj←ptor-1//注意，j指向p到r-1，不是r。doifA[j]≤xtheni←i+1exchangeA[i]<->A[j]exchangeA[i+1]<->A[r]returni+1然后递归排序整个数组：QUICKSORT(A,p,r)ifp28713564(pivot)j指2<=4，所以i++，i也指2，2和2互换，原数组不变。j向后移动，直到指向1..2.j（指向1）<=4，所以i++，i指向8，ij28713564于是8和1交换，数组变为:ij217835643.j向后移动，指向3，3<=4，所以此时i++i指向7，ij21783564所以7和3进行交换，数组就变成了：ij213875644。继续移动j，发现没有小于4的数。因此，执行到了最后一步，也就是部分上面PARTITION(A,p,r)代码的第7行。因此，i向后移动一个单位，指向8ij21387564A[i+1]<->A[r]，即,8和4交换，所以数组最后变成如下形式，21347568ok，第一次快速排序完成。接下来的过程，略。不过有个问题，能不能找到这个版本和上面版本的优化？5.快速排序深入分析下面详细分析一下上面的优化版本，PARTITION(A,p,r)x←A[r]i←p-1forj←ptor-1doifA[j]≤xtheni←i+1exchangeA[i]<->A[j]exchangeA[i+1]<->A[r]returni+1下面我们对数组进行排序，每一步的变化过程为：ip/j28713564(pivot)ij21783564ij21387564i21347568从上面的过程可以看出j对整个数组扫描了一次，为只要遇到小于4的元素，i就会++，然后交换kj和ki。那么，为什么当j找到小于4的元素时我必须++？你想，如果我一直呆在原地，那么每次交换的ki和kj不都是同一个元素吗？谈论排序？所以j在前面开路，i在j后面。只要j遇到小于4的元素，i就往前走一步，然后把j找到的小于4的元素赋值给i，然后j就重新开始往前走。打个比方，你可以认为我走的每一步都必须是一个小于4的元素，否则我无法继续前进。就好像j是先行者，为i开路，把小元素放在i前面作为跳板，为它前进铺路。这里j扫描到***，已经把小于4的元素全部查出来了，只有***一个pivot4，交给i处理，因为最后一步是exchangeA[i+1]<->A[r]。这样一来，不仅完全保证只要把小于4的元素交换到数组前面，把j之前没有处理过的更大的元素交换到后面，还是O(N)时间复杂度，不得不佩服这个算法的巧妙设计。这样一来，我有个疑问，上面的PARTITION(A,p,r)版本可以改成这样吗？希望读者思考一下：PARTITION(A,p,r)//版本请思考。x←A[r]i←p-1forj←ptor//让j从p指向***一个元素rdoifA[j]≤xtheni←i+1exchangeA[i]<->A[j]exchangeA[i+1]<->A[r]//去掉这***步returni//返回i，不再返回i+1。六、Hoare变体版本和优化版本的对比下面我们来讨论一个问题，在快速排序中，对于序列的划分，我们可以看到上面已经有两个版本，那么这两个版本哪个更好呢？好了，不着急，我们来对比一下：为了方便查看，再贴一下，看看各自的算法，Hoare变体版本：HOARE-PARTITION(A,p,r)x←A[p]//取第一个元素为主元素i←p-1j←r+1whileTRUEdorepeatj←j-1untilA[j]≤xrepeati←i+1untilA[i]≥xifiA[j]exchangeA[i+1]<->A[r]returni+1我们拿上面提到的霍尔版本的例子，对序列进行排序38712564：霍尔变体版本（以3为主，红体为主）：387125642871564//交换1次，比较4次2718564//交换1次，比较1次2178564//交换1次，比较1次2178564//交换1次，比较0次21378564//总交换4次，比较6次。//移动了元素3,8,7,1,2，移动范围为：2+3+1+2+4=12。优化版（以4为主要元素）：38712564//3和3交换不移动元素，比较一次31782564//交换一次，比较三次31287564//交换一次，比较一次31247568//交换一次，比较两次。//就完成了，一共4次交换，7次比较。//移动了元素8,7,1,2,4，移动范围为：6+2+2+2+4=16。又如：排序序列28713564：HoarevariantVersion:287135641873564//交换1次，比较5次1783564//交换1次，比较1次12783564//交换0次，比较1次。2填写，完成，共交流2次，比较7次。优化版：28713564//交换2和2，比较1次21783564//交换1次，比较3次21387564//交换1Times,compareonce21347568//交换一次，比较两次。完成，共4次交流，7次比较。女士们先生们，已经看到这两个例子说明不了任何问题。哪个版本更有效还有待进一步验证或数学证明。好吧，等以后找到更有利的证据我再论证。七、快速排序算法的时间复杂度还可以，我想你已经充分理解了这个快速排序，那么，我想你应该可以快速判断：快速排序算法的平均时间复杂度是O(nlgn)。为什么专栏？因为你看，j，我扫描一次数组，需要多少时间？顺便说一句，扫描一次，当然是O(n)，那么扫描列多少次，lgn到n次，最快的lgn，最慢的n次。并且可以证明，快速排序的平均时间复杂度为O(n*lgn)。在PARTITION能做的最均衡的划分中，得到的每个子问题不能大于n/2。因为其中一个子问题的大小是|_n/2_|。另一个子问题的大小为|-n/2-|-1。在这种情况下，快速排序要快得多。即：T(n)<=2T(n/2)+O(n)。可以证明T(n)=O(nlgn)。下面给出一个递归树的简单证明：在分治算法的三个步骤中，我们假设分解和合并过程所花费的时间为D(n)，C(n)，令T(n)是a的处理时间一个大小为n的序列消耗的时间是子序列的个数，每个子序列是原序列的1/b，α是将每个问题分解成α子-问题，则耗时为：O(1)如果n<=cT(n)=αT(n/b)+D(n)+C(n)在快速排序中，α为2，b也为2、然后分解（即取参考点，可以认为是1），合并（将数组合并成n），所以D(n)+C(n)是一个线性时间O(n)。这样，时间就变成了：T(n)=2T(n/2)+O(n)。如上图所示，每一层的时间复杂度为：O(n)，一共有Lgn层，每层为cn，所以总耗时为cn*lgn；总时间：cn*lg2n+cn=cn(1+lgn)为O(nlgn)。关于T(n)<=2T(n/2)+O(n)=>T(n)=O(nlgn)的严格数学证明，请参考《算法导论》第4章递归。那么，想请教各位读者一个问题，从快速排序算法的这个时间复杂度，你想到什么，你想到归并排序的时间复杂度，你想到二分查找，你想到一个有n个节点的类？红黑树的高度lgn，你有没有想过...8.上面说的快速排序想到的东西，早就想到了。这时，我想起了前几天看到的一个荷兰国旗问题。当时简单的和algorithm__和gnuhpc讨论过这个问题。现在具体解决这个问题：问题描述：我们把乱序的红、白、蓝球排列成颜色相同的红、白、蓝球有序的一组。这道题之所以叫荷兰国旗，是因为我们可以把红、白、蓝三色球想象成条状，有序排列后就形成了荷兰国旗。如下图所示：这个问题类似于快速排序中的分区过程。但是用了三个指针，一个是begin，一个是current，一个是end，两个互换。1.current遍历，整个数组序列，current表示1不动，2.current表示0，与begin交换，然后current++，begin++，3.current表示2，与end交换，然后current不动，end--.为什么，在第三步中，current指的是2，跟end交换后，current不动。是的，正如algorithm__所说：current之后的current++和begin++之所以和begin互换，是因为不用担心。今与末交换后，今不动，而末——是忧后。为什么呢，因为你想一想，你的最终目标无非就是把0、1、2有序排列。试想一下，如果第三步，在current和end交换之前，万一end之前end指0，而current交换之后，current现在指0，这个时候current能动吗？它不能移动，它指的是0，并且列必须与begin交换。好了，说了这么多，大家可能不是很清楚，直接参考gnuhpc的图，一目了然：本程序主体代码为：//quotedfromgnuhpcwhile(current<=end){if(array[current]==0){swap(array[current],array[begin]);current++;begin++;}elseif(array[current]==1){current++;}else//Whenarray[current]=2{swap(array[current]],array[end]);end--;}}看来这个问题和本文关系不大，不过，首先是其他文章中快速排序分区的过程类似，其次也是因为这个问题，一个小小的思考，终于成就了这篇文章。差点忘了，我还没有回答本文开头提出的问题。那么，快速排序算法是怎么想出来的，又是怎么一步步发明列的呢？答案很简单：多观察，多思考。ok，测试一下，看看你有没有多观察多思考的习惯：不知道有没有人真的想过冒泡排序。如果你想过，你想过如何改进气泡分选柱吗？ok，其他的我就不多说了，直接贴下图：本文到此结束。作者：七月
