说起快速排序，很多人都能够写出一个正确的快速排序，但就快速排序的正确性，就无从探究了。为什么说写出来的快速排序就是正确的。在快速排序中间的关键几步，以什么样的数据组织来保障快速排序的正确性。本文以《数据结构与算法 Java语言描述》中所描述的快速排序来进行理解，以查看其中的正确性。
首先查看排序的整体伪代码：
其中，中间所涉及的med算法如下所示：
以上即整个快速排序算法以及相对应的获取pivot的算法。
那么我们首先从源码上分析整个排序算法的正确性，以及在特殊的控制点上是如何取得正确的(在后续的说明中 小于的意思为小于或等于 大于的意思为大于或等于，即不对=pivot的数进行特殊处理)。
第1步
判断适用于快速算法的必要性，我们知道在一定范围之内，快速排序是不如插入排序的。这个范围依赖于具体的算法步骤分析。在本文中，这个范围被设定为CUTOFF，即如果这个排序的范围在CUTOFF之内，则就不再使用快速排序进行排序，而是直接使用插入排序对数据进行排序。排序完毕之后，即整个数组排序完毕。而且还有一个作用，即后续的排序方法中，整个数组的排序范围一定在大于CUTOFF处，这就保证了能够取得足够的数进行计算。
第2步
取得正确的pivot，即选出一个数据，来作为数组分组的中间数。在整个排序过程中，比这个数小(或等于)的数将排在数组的左边，而比之大(或等于)的数将排在右边。这个选择的过程由方法med(int[],int,int)来完成。它选择整个数组中最左边，最右边，以及中间的数进行比较，将处于中间数年作为pivot。
然后，在上面的med算法中，这个过程还将作更多的工作，这个工作即是对这三个数进行排序，保证最小的数放在a[left]位置上，最大的数放到a[right]上，而中间的数放在a[center]上。并且返回a[center]这个数。
值得注意的是，算法将a[center]和a[right-1]即倒数第二个数进行交换。
通过解读后面的算法得知，在进行a[left],a[center],a[right]之间的数据交换之后，在后续的判断当中，将不再对a[left],a[right]进行数据判断和交换工作，因为在这里已经作了一次处理了。而将a[center]与a[right-1]作为交换，是因为要将a[center]放到数组的最后，避免在数据处理过程中被交换了。
第3步，第4步
整个排序的核心部分，即比较并交换部分。首先，将左起点设为left,右起点设为right-1。但这两个点的数并不参与比较，因为在前面的med算法中已经进行处理过了。我们知道left比pivot，right-1即为pivot，而right比pivot大。所以在整个循环过程中，首先即对起点进行了+1操作，以将比较操作往前+1，以跨过最开始的起点。我们来看这两个比较和交换的代码：
第一个正确性：i和j永远不会越界，这是因为a[right]是比pivot大的，所以i一定会停止，而a[left]是比pivot小的，所以j也一定会停止。当两种情况的任意一种产生时，在后续的比较中，都会停止while，而导致i和j最终停止处理。
第二个正确性：当这两次比较过程中,i和j的位置有3种情况。ij。
对于第一种情况，即i和j没有相遇，这是最常见的一种情况。在没有相遇的情况下，a[i]所处的点，大于pivot，而a[j]所处的点小于pivot，这时将在后续处理中，交换这两个点，并且将在下一次循环中再一次移动i和j。
对于第二种情况下，即a[i]=a[i]=pivot，这时，并不需要交换i和j，因为它们本身即在同一个点上。
对于第三种情况，即在相遇时碰到的最常见的情况，即a[i]在一个比pivot大的一个点上，而当j=i的情况，判断出a[j]大于pivot，而自然进行下一步的–操作，这时即产生了i>j的情况，通常情况下都是i=j+1，即j在i有前一格。
对于上面的三种情况，第二种情况和第三种情况，均会使得while循环中止，对于第一种情况，将继续进行循环，最终达到第二种或第三种情况以达到中止的状态。
第三个正确性：即在未发生第4步的交换之前,i之前(不包括i)的数据均小于pivot，而j之后的数据均大于pivot。
第四个正确性：在发生了交换之后，仍然保持第三个正确性。这是因为，交换过程中，并没有发生i和j的改变，第三个正确性仍然成立。
第5步
我们现在来分析一下，while中止时i所处的点对于pivot以及i之前的数据的情况。这个情况有利于分析第5步操作的必要性和正确性。
第一种情况：在通常的情况下，即第3步，第4步的操作过程中，i和j在数组的中间相遇。由上面的第3步，第4步分析过程中的第二正确性可以看出整个最外层的while(循环均会在当i=j或ipivot时循环才会退出)。而第三，四正确性保证了以i作为分界线两边数据被分成了2组，即a[i]大于pivot。
第二种情况：i从最开始的内层循环开始就没移动过，即i在left+1处，[left+1,rithg-2]均大于pivot，这种情况下。仍然满足以上的
特殊，因为a[left]小于pivot，而a[i]=a[left+1]大于pivot。
第三种情况：j从最开始的内层循环就没移动过，即j在right-2处,而此时i则在right-1处，即[left+1,right-2]均大于pivot。这种情况下，仍然满足以上的情况，因为a[left]小于pivot，而[left+1,right-2]均小于pivot,a[i]=a[right-1]大于(这里大于等于被认为大于)pivot。
由于上面三种情况下，均满足a[i]大于pivot，且i之前的数据均小于pivot，所以i自然地被认为是整个数组划分点的中点。且下一步的操作要将比较数移到正确的位置上来(它原来在right-1处)。 由于i点即为分界点，且a[i]大于pivot，所以这里，将两个点的数据交换，即a[i]为pivot，而原来的a[i]被移到a[right-1]处，仍然满足i之前的数据小于pivot即a[i]，而i之后的数据大于pivot即a[i]。在之前的判断中，均以pivot为比较，现在终于可以将pivot放到正确的地方了，即a[i]处。
第6步
在第5步之后，i作为分界点，分相应的数据已经划到正确的位置上，满足i之前的数据比a[i]小，i之后的数据比a[i]大，所以分别对前部分进行排序，对后部分进行排序。
整个排序部分结束。
在整个排序过程中，正是由正确而紧凑地代码保证了排序的正确性，包括pivot的寻找，以及下限和下限的保证，确保在过程中不会出现越界以及交换错误的情况出现。
相关文章：
作者： flym
I am flym,the master of the site:)查看flym的所有文章