介绍

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

示意图

image.png

递归的三大要素

第一要素：明确你这个函数想要干什么
第二要素：寻找递归结束条件
第三要素：找出函数的等价关系式

快排基本思想

  1. 选定Pivot中心轴
  2. 将大于Pivot的数字放在Pivot的右边
  3. 将小于Pivot的数字放在Pivot的左边
  4. 分别对左右子序列重复前三步操作
    1. 左递归
    2. 右递归

选取中轴 pivot（这里取首元素）， left 指向第一个元素下标， right 指向最后一个元素下标，
如果 arr[right] >= pivot ，则 right—
如果 arr[right] < pivot ，则 arr[left] = arr[right] ，left++

如果 arr[left] <= pivot ，则 left++
如果 arr[left] > pivot ，则 arr[right] = arr[left] ， right—

代码

  1. // 快速排序
  3. package main
  5. import (
  6.     "fmt"
  7. )
  9. func quickSort(left int, right int, arr *[8]int) {
  11.     // 保留 左右下标值，不参与运算, 只用来传递参数，定义运算边界，划分子问题
  12.     L := left // 值拷贝
  13.     R := right
  15.     // 递归结束条件
  16.     if left >= right {
  17.         return
  18.     }
  20.     // 中轴
  21.     pivot := arr[left]
  23.     // 从小到大排
  24.     for left < right {
  25.         for left < right && arr[right] >= pivot {
  26.             right--
  27.         }
  28.         if left < right {
  29.             arr[left] = arr[right] // 移动值
  30.         }
  32.         for left < right && arr[left] <= pivot {
  33.             left++
  34.         }
  35.         if left < right {
  36.             arr[right] = arr[left]
  37.         }
  39.         if left >= right {
  40.             arr[left] = pivot
  41.         }
  42.     }
  43.     fmt.Println(left, right, arr)
  45.     // 划分子问题
  46.     // 左递归
  47.     quickSort(L, right-1, arr)
  48.     // 右递归
  49.     quickSort(right+1, R, arr)
  50. }
  52. func main() {
  53.     // arr := [6]int{-9, 78, 0, 23, -567, 70}
  54.     arr := [8]int{5, 8, 1, 3, 6, 2, 4, 7}
  55.     fmt.Println("arr = ", arr)
  56.     quickSort(0, len(arr)-1, &arr)
  57.     fmt.Println("arr = ", arr)
  58. }
  60. /*
  61. arr =  [5 8 1 3 6 2 4 7]
  62. 4 4 &[4 2 1 3 5 6 8 7]
  63. 3 3 &[3 2 1 4 5 6 8 7]
  64. 2 2 &[1 2 3 4 5 6 8 7]
  65. 0 0 &[1 2 3 4 5 6 8 7]
  66. 5 5 &[1 2 3 4 5 6 8 7]
  67. 7 7 &[1 2 3 4 5 6 7 8]
  68. arr =  [1 2 3 4 5 6 7 8]
  69. */