Go 数据结构和算法篇（八）：快速排序
今天
以下文章来源于xueyuanjun ，作者xueyuanjun
xueyuanjun学院君的订阅号，我会在这里持续更新优质全栈编程技术教程，包括但不限于 Golang、PHP、JavaScript 以及计算机底层技术。关注我，学习更多编程知识！
一、实现原理
归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。
快排的核心思想是这样的：
如果要排序数据序列中下标从 p 到 r 之间的一组数据，我们选择 p 到 r之间的任意一个数据作为 pivot（分区点），假设对应下标是 q。
遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数据序列 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
图示如下：
根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了，而且你可以看到我们不需要像归并排序那样做合并操作，也就不需要额外的内存空间，在时间复杂度和归并排序一样的情况下，有着更好的空间复杂度表现。
快速排序首先要找到分区点 pivot，一般我们会将数据序列最后一个元素或者第一个元素作为 pivot。假设我们以最后一个元素作为分区点，然后通过两个变量 i 和 j 作为下标来遍历数据序列，当下标 j 对应数据小于pivot 时，交换 i 和 j 对应的数据，并且将 i 的指针往后移动一位，否则 i 不动。下标 j 是始终往后移动的，j 到达终点后，将 pivot 与下标i 对应数据交换，这样最终将 pivot 置于数据序列中间，[0...i-1] 区间的数据都比 pivot 小，[i+1...j] 之间的数据都比 pivot 大，我们以递归的方式处理该流程，最终整个数据序列都会变成有序的，对应的算法操作流程如下：
二、示例代码
将上述流程转化为 Go 代码实现如下：
package main
import "fmt"
// 快速排序入口函数func quickSort(nums []int, p int, r int) { // 递归终止条件 if p >= r { return } // 获取分区位置 q := partition(nums, p, r) // 递归分区（排序是在定位 pivot 的过程中实现的） quickSort(nums, p, q - 1) quickSort(nums, q + 1, r)}
// 定位 pivotfunc partition(nums []int, p int, r int) int { // 以当前数据序列最后一个元素作为初始 pivot pivot := nums[r] // 初始化 i、j 下标 i := p // 后移 j 下标的遍历过程 for j := p; j < r; j++ { // 将比 pivot 小的数丢到 [p...i-1] 中，剩下的 [i...j] 区间都是比 pivot 大的 if nums[j] < pivot { // 互换 i、j 下标对应数据 nums[i], nums[j] = nums[j], nums[i] // 将 i 下标后移一位 i++ } }
// 最后将 pivot 与 i 下标对应数据值互换 // 这样一来，pivot 就位于当前数据序列中间，i 也就是 pivot 值对应的下标 nums[i], nums[r] = pivot, nums[i] // 返回 i 作为 pivot 分区位置 return i}
func main() { nums := []int{4, 5, 6, 7, 8, 3, 2, 1} quickSort(nums, 0, len(nums) - 1) fmt.Println(nums)}运行上述代码，打印结果如下，表明快速排序成功：
三、性能分析
正如我们前面所说的，快速排序是原地排序算法，时间复杂度和归并排序一样，也是 O(nlogn)，这个时间复杂度数据量越大，越优于 O(n2)。
但是快速排序也有其缺点，因为涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法。
尽管如此，凭借其良好的时间复杂度表现和空间复杂度的优势，快速排序在工程实践中应用较多。
关于线性表结构的排序算法我们就简单介绍到这里，下篇教程，我们来给大家介绍著名的线性表结构查找算法 —— 二分查找。
（本文完）