快速排序

实现原理

归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序算法其实很简单，采用分治策略。步骤如下：

1. 选取一个基准元素（pivot）
2. 比pivot小的放到pivot左边，比pivot大的放到pivot右边
3. 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

快排的核心思想：
如果要排序数据序列中下标从 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 大，我们以递归的方式处理该流程，最终整个数据序列都会变成有序的，对应的算法操作流程如下：

动图演示

快速排序的算法原理:

• 从数列中挑出一个元素，称为 “基准”(pivot).
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作.
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

示例代码

将上述流程转化为 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(n2)。
但是快速排序也有其缺点，因为涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法。
尽管如此，凭借其良好的时间复杂度表现和空间复杂度的优势，快速排序在工程实践中应用较多。

优化改进

场景分析： 递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。
改进思路：递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。