深入理解java快速排序的正确性

    说起快速排序,很多人都能够写出一个正确的快速排序,但就快速排序的正确性,就无从探究了。为什么说写出来的快速排序就是正确的。在快速排序中间的关键几步,以什么样的数据组织来保障快速排序的正确性。本文以《数据结构与算法 Java语言描述》中所描述的快速排序来进行理解,以查看其中的正确性。

    首先查看排序的整体伪代码:

public static void quicksort(int[] a, int left, int right) {
                //第1步
		if(left + CUTOFF > right) {
			insertsort(a, left, right);
			return;
		}
                //第2步
		int pivot = med(a, left, right);
                //第3步
		int i = left, j = right - 1;
		while(true) {
			while(a[++i] < pivot)
				;
			while(a[--j] > pivot)
				;
                        //第4步
			if(i < j)
				swap(a, i, j);
			else
				break;
		}
                //第5步
		swap(a, i, right - 1);
                //第6步
		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	}

    其中,中间所涉及的med算法如下所示:

private static int med(int[] a, int left, int right) {
		int center = (left + right) / 2;
		if(a[center] < a[left])
			swap(a, left, center);
		if(a[right] < a[left])
			swap(a, left, right);
		if(a[right] < a[center])
			swap(a, center, right);
		swap(a, center, right - 1);
		return a[right - 1];
	}

    以上即整个快速排序算法以及相对应的获取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,以跨过最开始的起点。我们来看这两个比较和交换的代码:

                        while(a[++i] < pivot);
			while(a[--j] > pivot);

    第一个正确性:i和j永远不会越界,这是因为a[right]是比pivot大的,所以i一定会停止,而a[left]是比pivot小的,所以j也一定会停止。当两种情况的任意一种产生时,在后续的比较中,都会停止while,而导致i和j最终停止处理。
    第二个正确性:当这两次比较过程中,i和j的位置有3种情况。i<j,i=j,或者i>j。
    对于第一种情况,即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或i<j的情况下退出循环),在这两种情况下,均可以得出a[i]大于pivot,这是由a[++i]的先行性while循环判断决定的(即只有当a[i]>pivot时循环才会退出)。而第三,四正确性保证了以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的寻找,以及下限和下限的保证,确保在过程中不会出现越界以及交换错误的情况出现。

转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201108210001.html

相关文章:

作者: flym

I am flym,the master of the site:)

《深入理解java快速排序的正确性》有2个想法

  1. 我今天看这本书的时候,脑袋都想大了。最关键的就是pivot放到了Right-1的位置上,一下就晕了。幸好我用“快速排序 Right – 1”的关键字搜到了你的博客 -_-!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注