快速排序是由东尼·霍尔所发明的一种排序算法，时间复杂度是 O(nlogn)， 是不稳定排序算法。
快速排序使用分治思想，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法演示
通过动图来演示一下这个算法的执行过程：
- 从数列中挑出一个元素，作为基准（pivot）。
- 重新排序数列，所有比基准小的值放到基准前面，所有比基准大的值放到基准后面。排序之后，基准值便处于数列的中间位置，这个过程称为分区。
- 再递归对两个子序列分别进行排序操作。
Go 语言实现
代码如下：
- package main
- import "fmt"
- func partition(list []int, low, high int) int {
- // 选择基准值
- pivot := list[high]
- for low < high {
- // low 指针值 <= pivot low 指针右移
- for low < high && pivot >= list[low] {
- low++
- }
- // low 指针值 > pivot low 值移到 high 位置
- list[high] = list[low]
- // high 指针值 >= pivot high 指针左移
- for low < high && pivot <= list[high] {
- high--
- }
- // high 指针值 < pivot high 值移到 low 位置
- list[low] = list[high]
- }
- // pivot 替换 high 值
- list[high] = pivot
- return high
- }
- func QuickSort(list []int, low, high int) {
- if high > low {
- // 分区
- pivot := partition(list, low, high)
- // 左边部分排序
- QuickSort(list, low, pivot-1)
- // 右边部分排序
- QuickSort(list, pivot+1, high)
- }
- }
- func main() {
- list := []int{2, 44, 4, 8, 33, 1, 22, -11, 6, 34, 55, 54, 9}
- QuickSort(list, 0, len(list)-1)
- fmt.Println(list)
- }
以上就是本文的全部内容。
参考文章：
- https://mojotv.cn/algorithm/golang-quick-sort。
原文地址：https://mp.weixin.qq.com/s/OaHrvRGyVEWEC4gyONan1Q
