快速排序详解（精细到每一帧）

说到排序算法，很多小伙伴都并不陌生。快速排序作为排序算法中时间复杂度较低 (O(n * logn) 的一种，在许多其他算法中都有重大作用。本文将试图从最细致到角度，将快速排序算法的每一帧变化都还原出来，给让小伙伴们还原来自算法的美

算法背景

快速排序思想的本质是来源于冒泡排序，冒泡排序是通过比较相邻的两个元素，每次将最小的元素调换到最顶端。显而易见，对于长度为5的数组，共需要比较 4 + 3 + 2 + 1次。所以冒泡排序的时间复杂度(Time Complexity)是O(n * n), 当我们需要更快的排序算法时，一种思路是使用递归来辅助排序，1960年快速排序应运而生。

基本原理

Quick Sort快速排序的关键是规定排序点Pivot, 然后给数组两边各放一个指针。当左指针指向的数大于等于排序点Pivot，而右指针指向的点小于等于排序点Pivot时，交换两点数值。当右指针位于左指针左侧时，停止循环并开启左右两次递归。

具体样例

当数组 l = [3, 20, 1, 6, 11, 9, 15] 时：我们取迎面双指针，左指针指向数组起始点Start，右指针指向数组终止点End

对于中间值 Pivot取数组两端的中间值

Pivot = (Nums[start] + Nums[end]) / 2 Pivot = (3 + 15) / 2 = 9

下一步开始从左指针开始移动：

对于左 (Left) 指针 3 < 9, 满足左指针右移条件

发现20的值大于Pivot，左指针停止

开始将右指向左移动移动，直到发现9小于等于Pivot 9

交换左右指针指向的值

由于交换过后左右指针指向的数必然满足要求（左指针小于Pivot，右指针大于Pivot）

左 (Left) 指针继续向左移动右 (Right) 指针继续向右移动各一位

1小于9，左指针右移

6小于9，左指针右移

11大于9，左指针不动。排查右指针， 11大于9，满足右指针移动条件，右指针左移

右指针（绿色指针）位于左指针左侧， While循环跳出数组分成两部分：

左侧数组由数组起始位置（start）到右侧数组由Left指针（红色指针）

Right指针（绿色指针）的最终位置的最终位置到数组结束位置（end）

对于左边数组(黄色数组)： Pivot = (Nums[start] + Nums[end]) / 2 Pivot = 4.5

对于右边数组(粉色数组)： Pivot = (Nums[start] + Nums[end]) / 2 Pivot = 13

再增加一层递归：

当长度为一时数组返回，这样排序就完成了

代码实现

Python

def quicksort(nums, start, end):
	if start >= end:
		return
	
	i, j = start, end
	pivot = (nums[start] + nums[end]) / 2
	while i <= j:
		while i <= j and nums[i] < pivot:
			i += 1
		while i <= j and nums[j] > pivot:
			j -= 1
		if i <= j:
			nums[i], nums[j] = nums[j], nums[i]
			i += 1
			j -= 1
	
	quicksort(nums, start, j)
	quicksort(nums, i, end)
	return

快速排序算法的时间复杂度时O(n * logn), 空间复杂度是O(n). 巧妙地使用了递归的思路加快了排序的进程。类似的时间复杂度为N的算法还有归并排序和选择排序。