快速排序算法的思想

快速排序是利用分治思想实现的排序算法，其思路描述为：

在待排序的数组中选定一个枢轴元素，然后按照这个元素划分整个数组，使得比该元素小的元素都在一侧，比该元素大的元素都在另一侧，升序排序的情况下，就是较小的在左侧，较大的在右侧；
因为划分后枢轴元素已经位于最终排序数组中准确位置上（即一直到排序完成，枢轴元素的位置都不用再次改变），所以只需要把递归处理枢轴前的区间和枢轴后的区间，也就是通过划分和递归，把排序问题分而治之；
如果一个区间只有一个元素，天然有序，直接返回，否则继续划分-递归的步骤，直到数组排序完成。

快速排序算法的实现

实现快速排序算法的难点是实现一个枢轴划分函数 partition，实现 partition 函数之后，只需要按照划分-递归的思路实现 quickSort 即可，Go 语言的一种实现方式如下：

func partition(arr []int, l, r int) int {
	base := arr[l]
	i, j := l, r
	for i < j {
		for i < j && arr[j] >= base {
			j--
		}
		arr[i] = arr[j]
		for i < j && arr[i] <= base {
			i++
		}
		arr[j] = arr[i]
	}
	arr[i] = base
	return i
}

func quickSort(arr []int, l, r int) {
	if l >= r {
		return
	}
	mid := partition(arr, l, r)
	quickSort(arr, l, mid-1)
	quickSort(arr, mid+1, r)
}

快速排序的延申应用

寻找数组中第K小（大）元素，最小（最大）的 K 个元素

因为选定枢轴元素并划分完成后，该枢轴元素的右边元素都比它大，左边元素都比它小，所以如果一次划分返回枢轴元素的下标为 m, 那么该位置的元素就是数组中的第 m 小元素，也是第 len(array) - m 大的元素，数组中的前 m 个元素就是数组中最小的K个元素，那么这种划分可以用来求第 K 小（大）元素或较小（大）的 K 个元素，具体思路如下：

目标：求数组 nums 中第 K 小元素
算法：
- 对数组进行一次划分，返回的小标为 m
- 如果 m == K-1, 返回nums[m], 否则：
- 如果 K-1 < m, 继续划分数组以m为界限的左边部分，否则，划分右半部分
- 直到 m == k-1

需要注意的是，这种思路借助了快排思想，而快排是一种内部排序算法，即需要把所有元素加载到内存中，因此，这种算法只适合求解内存能容纳的大小的数组的求解，不适合在海量数据（或者数据流）中寻找第 K 大的元素。

此类问题还有一种求解思路是借助小顶堆（大顶堆求解），如果寻找第K大元素或者最大的K个元素，就用小顶堆，相反的，求第K小或者最小的K个元素就用大顶堆。

面试中遇到类似问题，一定要分清场景，如果是输入是个数组，一般两种方法都可行，如果输入是存在数据库或者磁盘中的海量数据，或者一直持续传入的数据流，一般只适用堆的方法。

双指针划分思路的其他应用

这篇博客中的划分，是用一种类似双指针的思路的原地划分思路，不需要额外的内存空间，可以文字描述为：

两个指针 i, j 分别指向数组首尾元素，先用一个外部变量 base 存储 nums[i] 的元素，那么相当于取走了 nums[i] 中的元素，nums[i]是空的；
当 i < j 时：
- 因为 nums[i] 是 "空的", 那么便从数组右侧找到一个小于 base 的元素 nums[j], 将 nums[j] 存入 nums[i], 此时nums[j] 是"空的"；
- 因为 nums[j] 是 "空的", 那么便从数组右侧找到一个小于 base 的元素 nums[i], 将nums[i] 存入 nums[j], 此时nums[i] 是"空的"；
- i == j 之前不断循环
循环退出后，i == j 并且 nums[i] 是"空的", 将 base 存入 nums[i]

以上思路可以适用于其他的数组划分问题，比如有一个问题是，将给定数组按照奇数在左侧，偶数在右侧划分，这个问题完全可以借用上述算法，从右侧找奇数放到左侧，从左侧找偶数放到右侧，便可以 O(n) 时间复杂度完成原地划分。