算法之6分治法实现快速排序

2.6 快速排序(quick sort)

2.6.1 算法思路

整体思路：随机选一个数，把比它大的数放在它的右边，小的放在左边，那个数所在的位置，就会是它最终排序所在的位置。然后继续排左右两边的数，按这种思路往下递归。

细节步骤：随机选择的那个数，我们称之为“基准数”。

• ① 设置基准数。随机选择一个数为基准数，把基准数和首元素交换位置
• ② 移动指针。设置左指针和右指针，左指针从左往右移动，一旦找到比基准数大的元素就停下来，然后左指针从右往左移动，一旦找到比基准数小的元素就停下来，然后把它俩互换位置，同理，左右指针继续向中间移动，直到两个指针重合或者错位
• ③ 插入基准数。基准数如果比右指针的元素小，就把基准数和右指针的左边一个元素互换位置，如果基准数比右指针的元素大，就把基准数和尾指针元素互换。
• ④ 递归。基准数的左右两部分继续进行排序。

请问，步骤④中：

• 当基准数比右指针的元素小，为什么不可以是把基准数和左指针交换？
• 基准数如果比右指针元素大，为什么是把基准数和尾指针元素互换？
• 基准数如果比右指针元素大，是否可以把基准数和右指针右边的一个数交换?

回答：

• 1.因为左右指针可能位置重合。
• 2.(看代码)但凡右指针有移动过，则右指针所指元素必然大于等于基准元素，如果右指针元素小于基准元素，则说明右指针必然没有移动过，此时右指针跟尾指针重合。如果右指针元素等于基准元素，意味着右指针及其右侧的元素(如果存在的话)都必然等于基准元素，所以直接把基准元素跟尾指针元素互换，没有问题。
• 3.不可以，若右指针是尾指针，其右侧将发生越界。

2.6.2 代码实现

//	快速排序
public static int[] quickSort(int[] originalData) {
	int [] sortedData=originalData.clone();
	QSRecursion(sortedData,0,sortedData.length-1);
	return sortedData;
}

private static void QSRecursion(int[] sortedData, int head, int tail) {
	if(head==tail)return;//如果只有一个元素，则无需排序
	int partitionIndex=head+new java.util.Random().nextInt(tail-head+1);//随机选择一个数，设置为基准元素
	int pivot=partition(sortedData,head,tail,partitionIndex);//保存基准元素排好的位置
	if(pivot!=head)QSRecursion(sortedData,head,pivot-1);//如果基准元素不在第一位，则继续将其左边的序列进行排序
	if(pivot!=tail)QSRecursion(sortedData,pivot+1,tail);//如果基准元素不在最后一位，则继续将其右边的序列进行排序
}

private static int partition(int[] sortedData, int head, int tail, int partitionIndex) {
	swap(sortedData,head,partitionIndex);//将首元素和基准元素对换位置
	int left=head+1;
	int right=tail;
	while(left<right) {
		while(sortedData[left]<=sortedData[head]&left<right) {
			left++;
		}
		while(sortedData[right]>=sortedData[head]&left<right) {
			right--;
		}
		if(left<right) {
			swap(sortedData,right,left);//对换位置,保证左小右大
		}
	}
	/*核心代码，易错点*/
	if(sortedData[right]>sortedData[head]) {
		swap(sortedData,right-1,head);
		partitionIndex=right-1;
	}else {
		swap(sortedData,tail,head);
		partitionIndex=tail;
	}
	return partitionIndex;
}

2.6.3 时间复杂度

最坏情形：Θ(n²）
分析：最坏情形类似于选择排序，就是每次选择的基准数都是最大或者最小的数，此时快速排序每一次递归，需要比较n次，n次递归后才排好所有的数，所以最坏情形的时间复杂度n²。
最好情形：Θ(nlog₂n)
分析：最好情形类似于合并排序，就是每次选择的基准数都是中位数，此时快速排序每一次递归，需要比较n次，log₂n次递归后排好所有的数，所以最好情形的时间复杂度nlog₂n。