Go 数据结构和算法篇（八）：快速排序

一、实现原理

归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。

快排的核心思想是这样的：

如果要排序数据序列中下标从 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)
}

// 定位 pivot
func 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(n²)。

但是快速排序也有其缺点，因为涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法。

尽管如此，凭借其良好的时间复杂度表现和空间复杂度的优势，快速排序在工程实践中应用较多。

关于线性表结构的排序算法我们就简单介绍到这里，下篇教程，我们来给大家介绍著名的线性表结构查找算法 —— 二分查找。