快速排序及其优化

快排由于其常数项比其他O(N*log(N))级别的排序算法低，是工程中常用的一种排序算法，但是排序算法的跨元素交换的特性也使得快排失去了稳定了，故常用于基本数据类型的排序；经典快排是对冒泡排序的一种改进，因此一次排序依然只能确定一个元素的位置，并且对于趋近于有序的数据状况，快排的时间复杂度反而会变差。本文以经典快排为基础，讨论一下对于快速排序算法的优化。

经典快排

快速排序是基于冒泡排序的一种改进，如何理解这句话？冒泡排序基于相邻元素两两之间的比较，每一轮冒泡确定当前未排序列中的一个最值，这样来看冒泡的方向是单向的，并且每轮冒泡的数量是单个的，确实有些低效。我们考虑能否同时向两边冒泡，且每轮冒泡的数量可以是多个，要实现这个目的，我们必须定一个标准，为什么这么说？在冒泡排序中，我们只是单侧从头到尾的冒泡，这样即使每次比较没有统一的参照标准，两两比较也必然能够找出本轮的最值，但要想往两边冒泡，我们却只能从一边开始遍历的情况下，只能设定一个统一的比较标准，根据这个标准将当前序列中的数分为两部分，实现双向冒泡的同时使得每轮有多个元素进行冒泡。

基本思想

经典快排的过程是将给定数组根据某一标准（通常是数组的第一个元素或最后一个元素）划分成两个部分，小于等于标准的元素放左边，大于标准的元素放右边，同时确定标准的最终位置；进而递归调用该方法，划分标准左侧的部分和标准右侧的部分。递归调用过程如图所示：

如图所示，橙色位置的元素表示该元素已经完成了最终位置的交换，且此时整个序列中该元素以左一定小于该元素，以右一定大于该元素；第一次调用确定一个元素的位置，第二次调用再确定两个元素的位置……以此类推，呈指数级增长，直到划分出某个标准两侧出现单个元素时不再进行划分。

算法实现

下面我们来分析这个算法应当如何实现，首先既然是递归函数，依然遵循我们构建递归函数的流程，考虑以下两个问题：

1. base case：递归的终止条件如上面所说，当要划分的区间为单个元素时停止；
2. 依赖关系：当我们再去考虑依赖条件时会发现一件有趣的现象，那就是快排的递归函数根本不存在依赖关系，因为当我们要对子问题做划分的前提是我们先确定划分标准的位置，而当这个位置确定的时候，当前已经是关于划分点左右有序的次序关系了，因此左右两个子部分下一次递归划分的过程和结果不再会对上一轮已经确定的划分点位置产生影响；这就说明我们其实可以将子问题计算的过程从串行计算改成并行计算，对并行算法有研究的同学可以做一下这方面的尝试。

下面我们来看一下经典快排的算法实现代码：

public static void quickSort(int[] arr) {
	if(arr==null||arr.length<2)
		return;
	quickSort(arr, 0, arr.length-1);
}
public static void quickSort(int[] arr,int left,int right) {
	if(left<right) {
		int pivot = partition(arr, left, right);
		quickSort(arr, left, pivot);
		quickSort(arr, pivot+1, right);
	}
}

其中，pivot变量代表每一次子部分的排序后划分点的下标位置，而left和right也限制了子问题的范围，当子部分的区间大小只有一个元素时停止划分。我们可以通过对比快排的递归函数和归并排序的递归函数发现为什么快排的递归过程不存在依赖关系而归并排序的递归过程存在依赖关系，从代码的执行顺序来看，归并排序是先调用递归函数，再进行合并；而快排是先进行排序，确定划分点，再调用递归函数。这件事情的实质是归并排序如果子部分还无序，那么是子部分之间是无法进行合并的；而快排是即便子部分还是无序，子部分之间的划分点位置已经确定，不再受子部分的排序结果影响，这才是递归函数依赖关系的核心。

下面我们来分析一次排序的过程，即partition这个函数的实现，前面我们一直在说划分标准这件事，但是上面的递归函数中并没有相关的代码逻辑，那么在确定划分点这个函数中我们首先要确定划分标准，这里不妨用子部分中的最后一个元素来做划分标准，最后确定好划分点位置之后将该元素交换过来即可。剩余的部分我们需要考虑如何将每次比较的结果保存下来，由于经典排序的一次只确定一个数的位置，我们可以将整个子部分按照从左往右的顺序分成四部分：

1. 小于等于部分：元素值小于等于划分标准的部分
2. 未排序部分：元素还未排序的部分
3. 大于部分：元素值大于划分标准的部分
4. 划分标准：排序阶段，最后一个元素作为划分标准不参与其他元素的交换

整个排序的过程如下图所示：

图中根据不同分布使用不同颜色进行区分，在排序的过程中大致可以分为这几种情况：

1. 初始值的设定：未排序部分的指针位于第一个元素处，即小于等于部分还没有元素；大于部分的指针指向不参与排序的划分标准处，即大于部分还没有元素；
2. 当比较结果为小于等于时（smaller），当前指针向后移动，该元素归入小于等于部分；
3. 当比较结果为大于时（bigger），more指针向前移动，交换more和current指向的元素，current指针驻停，被交换的元素归入大于部分；
4. 当current指针和more指针相邻时结束遍历，交换more指针指向元素和划分标准的位置，返回more的数组下标。

下面我们来看一下代码：

public static int partition(int[] arr,int left,int right) {
	//情况1
	int current = left;
	int more = right;
	//情况4（终止条件）
	while(current < more) {
		//情况3
		if(arr[current] > arr[right])
			swap(arr, current, --more);
		//情况2
		else
			current++;
	}
	//情况4
	swap(arr, more, right);
	return more;
}

注意：代码中的current遍历完全可以使用形参中的left替代，这里为了和分析图中的遍历保持一致多申请了current这个变量。

算法剖析

代码的逻辑非常简单，即上述图中所解释的几种情况，下面我们来分析一下算法的时间复杂度和空间复杂度。经典快排的时间和空间复杂度是取决于要排序的数据状况的，且数据状况越接近有序，经典快排的时间和空间复杂度越差，这又是什么原因呢？

回顾上面我们在描述经典快排算法思想的递归调用过程图，仔细思考一下我们会发现经典快排有一个严重的问题，就是它非常依赖于划分点在整个序列最终确定的位置，如果每一次划分点的位置都接近序列的中间位置，那么整个递归调用过程的次数就会很少，需要申请用于存储划分点位置的额外空间也会相应减少，反之则整个算法的时间复杂度和空间复杂度都会变差。

首先我们来看算法的空间复杂度，虽然这一算法在递归调用过程中不存在依赖关系，但也不代表子过程不需要父过程中的任何有效信息，不论是观察调用图还是递归函数结构，我们都可以发现划分点的位置信息，在两个子过程中都有传递，那么该信息其实在递归调用过程中是申请了非常数级的额外空间的，即只有将每一个子过程的划分点位置保留下来，函数才能够在左部分递归完毕后找到右部分开始递归的位置。

那么这个额外的空间复杂度是多少呢？这里就涉及到所要排序的序列是一个什么样的数据状况了，如果每一次的划分都正好将子部分均分，那么这个算法的空间复杂度就是整个序列能够被二分多少次的次数，即以2为底的N的对数，空间复杂度为O(log(N))；反之如果每一次划分点的位置都很偏向整个序列的边缘，那么基本上每个元素都将作为子部分的划分点被记录下来，故需要额外申请N个辅助空间来存储，空间复杂度为O(N)。

时间复杂度的推导也是同理，如果每一次的划分都正好将子部分均分，那么这个算法的时间复杂度就可以用master公式去估计（符合子问题等规模划分的前提），其中a=b=2 =》 log(a,b)=1且d=1 =》 算法的时间复杂度T(N)=O(N*log(N))；反之如果每一次划分点的位置都很偏向整个序列的边缘，那么后序的划分中较短的一侧很快会划分到单个元素，而另一次却要经历更多的子过程划分才能划分为单个元素的子部分。举一个极端的例子，如果待排序的整个序列呈逆序，那么使用快排一次只能确定出最边缘的一个元素的位置，整个算法退回O(N²)的时间复杂度，这样的情况显然是我们不想看到，因此我们有必要对经典快排做一些修改和优化。

• 空间复杂度：最好O(log(N))，最差O(N)
• 时间复杂度：最好O(N*log(N))，最差O(N²)

荷兰国旗问题

讨论快排之前，我们先来引入一个经典的荷兰国旗问题，这个算法的思想接下来会为我们优化快排提供思路。

• 题目：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

• 要求：额外空间复杂度O(1)，时间复杂度O(N)

• 对数器：使用额外空间对数组进行拷贝，三次遍历原数组分别找出小于、等于和大于给定数的元素依次拷贝到辅助数组，再拷贝回原数组。

• 分析：荷兰国旗问题实质上是对序列的一种排序，并非序列中的每个元素都要严格按照从小到大的升序或从大到小的降序，而仅仅是对某一个值或某几个相等值的位置进行确定，这个位置指的是如果整个序列有序，那么给定值的位置应该处于哪里（有可能给定值位于序列之外）。由于这个最重要确定位置的值是已知的，那么我们就要思考如何利用这一有效信息，来尽可能的让每一次的比较信息都有所保留，这样才能降低算法的时间复杂度。在经典的冒泡排序算法中，由于缺少一个参照的对象，只能从头到尾依次比较，将每一轮的最大值或最小值冒泡出来，但是这样进行冒泡除了能够确定下一次的最值之外，无法提供更多的有效信息，因为最值的位置无疑是确定的，即从边界向中间不断推进，即使我们不清楚这一轮的最值是多少，也知道他的位置已经其余元素和最值之间的相对次序关系；而在我们将最值逐渐冒泡到边界的过程中，我们不只是比较了最值和其他元素的大小关系，同时也比较了部分非最值之间的大小关系，而这些信息在冒泡排序的过程中没有能够很好的利用。在荷兰国旗问题中，已知要确定位置的值的情况下，充分利用序列中的元素每一次和该值比较所得的相对次序，是解决这一问题的核心。

• 思路：我们可以在遍历序列的过程中，有意识的将整个数组划分为四个部分，分别是

  • 小于部分：其中的元素小于给定值

  • 等于部分：其中的元素等于给定值

  • 大于部分：其中的元素大于给定值

  • 未排部分：其中的元素还未进行比较

    初始情况下，整个数组都是未排部分，其余三个部分为空，而在逐渐遍历和比较整个数组所有元素的过程中扩充其他三个部分，直到未排部分的元素为空，则该序列关于要确定位置的值的相对次序也最终确定。如图所示：

如图b所示，四个部分用三个指针进行分割，less指针以及之前的元素均为小于给定值的部分，more指针以及之后的元素均为大于给定值的部分，而current指针表示当前正在遍历比较的元素，其两侧分隔了等于给定值的元素和未比较的元素。

元素交换的逻辑也很简单，如图a所示，初始情况下所有元素都未经过比较因此都属于未排部分，less和more两个指针位于数组之外，current指针位于数组开始位置，current元素与给定值的比较无非分成三种情况：

1. 当前元素小于给定值：交换当前元素和less指针指向的下一个元素，并将less指针后移，小于部分扩充（图a绿线）
2. 当前元素小于给定值：不交换元素，current指针后移，即等于部分扩充
3. 当前元素大于给定值：交换当前元素和more指针指向的前一个元素，并将more指针前移，大于部分扩充（图a红线）

到这里，我们对于该算法的框架已经设计得比较完善了，下面就是代码中的细节问题，如何控制current指针移动的逻辑是需要特别注意的，第一和第二种情况中小于部分和等于部分的扩充都是指针向后移动，而第三种情况大于部分的扩充是指针向前移动，这两种不同的情况实质上的区别在于本次元素交换的来源，第三种情况与当前元素交换的元素来自未排部分，因此current指针的移动逻辑要却别开来。下面我们来看代码：

public static void partiton(int[] arr,int num) {
	int less = -1 , more = arr.length;
	boolean stay = false;
	for(int current = 0 ; current < arr.length ; current ++) {
		//情况三
		if(arr[current]>num) {
			more--;
			swap(arr, current, more);
			stay = true;
		//情况一
		}else if(arr[current]<num) {
			less++;
			swap(arr, less, current);
		}
		//情况三的current指针移动逻辑
		if(stay) {
			current--;
			stay = false;
		}
		//循环终止条件
		if(current==more-1)
			break;
	}
}

注意：代码中的元素交换函数由于不涉及本题的核心逻辑，采用伪代码实现，想要测试当前方法的同学请自行实现。

我们发现，代码中对于第三种情况，设置了布尔开关，即如果存在未排部分的元素与当前元素进行交换时，应该使current指针驻停，否则会导致未排部分元素的遗漏。同时，如果大于部分不为空，则遍历的终止条件是current指针和more指针的相邻（大于部分为空时也可以这么理解），代码中也给出了判断。

• 总结：荷兰国旗问题的解法向我们充分展示了如何将每一次的比较结果都记录下来，不论是大于，等于还是小于当前结果都会有合适的区间来保存比较结果，以便于后序对这些相对次序的再次利用，这个思路和归并排序中从组内有序到整体有序的合并过程也有着异曲同工之妙。

经典快排优化策略

荷兰国旗问题划分

经典快排一次只能确定一个元素的位置，面对相等元素较多的序列这样去逐个确定位置无疑是低效的，我们可以采用荷兰国旗问题的分割逻辑对快排的partition过程进行优化，这样我们每一次的返回值就不再是单个元素的下标位置，而是值相等的元素序列的起始位置和终止位置两个信息。这样的优化，相较于一次只能确定一个元素位置的经典快排，无疑是能够起到加速作用。

随机快排

对于上面分析到的经典快排对于数据状况的依赖问题，可以采用概率的方式降低依赖性，操作方式为每一次开始划分之前都在子序列中随机挑选一个元素，作为本轮划分的划分标准，这样一来，虽然仍然有可能出现较差的数据状况，但是此时对于算法的时间和空间复杂度的估算只能通过概率来估计，用长期期望的方式来计算时间复杂度。根据严格的数学证明，各种等概率的情况累加后得到基于长期期望的表达式结果是：时间复杂度O(N*log(N))，空间复杂度O(log(N))。

最后，我们将两种优化手段结合后的快排代码展示给大家：

public static void quickSort(int[] arr) {
	if(arr==null||arr.length<2)
		return;
	quickSort(arr, 0, arr.length-1);
}
public static void quickSort(int[] arr,int left,int right) {
	if(left<right) {
		//随机快排：划分值随机选择
		FoundSort.swap(arr, left+(int)(Math.random()*(right-left+1)), right);
		int[] equal = partition(arr, left, right);
		quickSort(arr, left, equal[0]-1);
		quickSort(arr, equal[1]+1, right);
	}
}
/**
 * 默认以最后一个数作为划分标准
 * @param arr
 * @param left
 * @param right
 * @return
 */
public static int[] partition(int[] arr,int left,int right) {
	int less = left - 1;
	//划分初始，默认的区域为arr【right】之前的所有范围，即划分完后整个区域分为四个部分
	//【小于arr[right]】【等于arr[right]】【大于arr[right]】【arr[right]】
	int more = right;
	while(left<more) {
		if(arr[left]<arr[right])
			swap(arr, left++, ++less);
		else if(arr[left]>arr[right])
			swap(arr, left, --more);
		else
			left++;
	}
	//收尾工作，将最后一位arr[right]纳入整个序列
	swap(arr, more, right);
	return new int[] {less + 1,more};
}

---