快速排序

    注： ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。

    本质上来看，快速排序是对冒泡排序的一种改进，属于交换类的排序算法。

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

    步骤如下：

    1. 先从数列中取出一个数作为基准数。一般取第一个数。
    2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
    3. 再对左右区间重复第二步，直到各区间只有一个数。

    举一个例子：5 9 1 6 8 14 6 49 25 4 6 3。

    快速排序主要靠基准数进行切分，将数列分成两部分，一部分比基准数都小，一部分比基准数都大。

    在最好情况下，每一轮都能平均切分，每一轮遍历比较元素 n 次就可以把数列分成两部分，每一轮的时间复杂度都是：O(n)。因为问题规模每次被折半，折半的数列继续递归进行切分，也就是总的时间复杂度计算公式为： T(n) = 2*T(n/2) + O(n)。按照主定理公式计算，我们可以知道时间复杂度为：O(nlogn)，当然我们可以来具体计算一下：

    1. 我们来分析最好情况，每一轮切分，遍历比较元素的次数为 n
    3. T(n) = 2*T(n/2) + n
    4. T(n/2) = 2*T(n/4) + n/2
    5. T(n/4) = 2*T(n/8) + n/4
    6. T(n/8) = 2*T(n/16) + n/8
    7. ...
    8. T(4) = 2*T(2) + 4
    9. T(2) = 2*T(1) + 2
    10. T(1) = 1
    12. 进行合并也就是：
    14. T(n) = 2*T(n/2) + n
    15.      = 2^2*T(n/4)+ n + n
    16.      = 2^3*T(n/8) + n + n + n
    17.      = 2^4*T(n/16) + n + n + n + n
    18.      = ...
    19.      = 2^logn*T(1) + logn * n
    20.      = 2^logn + nlogn
    21.      = n + nlogn
    23. 因为当问题规模 n 趋于无穷大时 nlogn 比 n 大，所以 T(n) = O(nlogn)。
    25. 最好时间复杂度为：O(nlogn)。
    27. 注：^ 表示乘方。

    最差的情况下，每次都不能平均地切分，每次切分都因为基准数是最大的或者最小的，不能分成两个数列，这样时间复杂度变为了 T(n) = T(n-1) + O(n)，按照主定理计算可以知道时间复杂度为：O(n^2)，我们可以来实际计算一下：

    1. 我们来分析最差情况，每一轮切分，遍历比较元素的次数为 n
    3. T(n) = T(n-1) + n
    4.      = T(n-2) + n-1 + n
    5.      = T(n-3) + n-2 + n-1 + n
    6.      = ...
    7.      = T(1) + 2 +3 + ... + n-2 + n-1 + n
    8.      = O(n^2)
    10. 最差时间复杂度为：O(n^2)。
    12. 注：^ 表示乘方。

    根据熵的概念，数量越大，随机性越高，越自发无序，所以待排序数据规模非常大时，出现最差情况的情形较少。在综合情况下，快速排序的平均时间复杂度为：O(nlogn)。对比之前介绍的排序算法，快速排序比那些动不动就是平方级别的初级排序算法更佳。

    1.2 空间复杂度

    快速排序使用原地排序，存储空间复杂度为：O(1)。而因为递归栈的影响，递归的程序栈开辟的层数范围在 logn ~ n，所以递归栈的空间复杂度为：O(logn) ~ log(n)，最坏为：log(n)，当元素较多时，程序栈可能溢出。通过改进算法，使用伪尾递归进行优化，递归栈的空间复杂度可以减小到 O(logn)，可以见下面算法优化。

    快速排序是不稳定的，因为切分过程中进行了交换，相同值的元素可能发生位置变化。

    切分的结果极大地影响快速排序的性能，比如每次切分的时候选择的基数数都是数组中最大或者最小的，会出现最坏情况，为了避免切分不均匀情况的发生，有几种方法改进：

    1. 随机基准数选择：每次进行快速排序切分时，先将数列随机打乱，再进行切分，这样随机加了个震荡，减少不均匀的情况。当然，也可以随机选择一个基准数，而不是选第一个数。
    2. 中位数选择：每次取数列头部，中部，尾部三个数，取三个数的中位数为基准数进行切分。

    方法 1 相对好，而方法 2 引入了额外的比较操作，一般情况下我们可以随机选择一个基准数。

    从一个数组中随机选择一个数，或者取中位数都比较容易实现，我们在此就不实现了，避免造成心智负担，下文代码实现都取第一个数为基准数。

    二、算法实现

    这是最普通的一种实现。

    1. package main
    3. import "fmt"
    5. // QuickSort 普通快速排序
    6. func QuickSort(array []int, begin, end int) {
    7.     if begin < end {
    8.         // 进行切分
    9.         loc := partition(array, begin, end)
    10.         // 对左部分进行快排
    11.         QuickSort(array, begin, loc-1)
    12.         // 对右部分进行快排
    13.         QuickSort(array, loc+1, end)
    14.     }
    15. }
    17. // 切分函数，并返回切分元素的下标
    18. func partition(array []int, begin, end int) int {
    19.     i := begin + 1 // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
    20.     j := end       // array[end]是数组的最后一位
    22.     // 没重合之前
    23.     for i < j {
    24.         if array[i] > array[begin] {
    25.             array[i], array[j] = array[j], array[i] // 交换
    26.             j--
    27.         } else {
    28.             i++
    29.         }
    30.     }
    32.     /* 跳出 for 循环后，i = j。
    33.      * 此时数组被分割成两个部分   -->  array[begin+1] ~ array[i-1] < array[begin]
    34.      *                        -->  array[i+1] ~ array[end] > array[begin]
    35.      * 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。
    36.      * 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！
    37.      */
    38.     if array[i] >= array[begin] { // 这里必须要取等“>=”，否则数组元素由相同的值组成时，会出现错误！
    39.         i--
    40.     }
    42.     array[begin], array[i] = array[i], array[begin]
    43.     return i
    44. }
    46. func main() {
    47.     list := []int{5}
    48.     QuickSort(list, 0, len(list)-1)
    49.     fmt.Println(list)
    51.     list1 := []int{5, 9}
    52.     QuickSort(list1, 0, len(list1)-1)
    53.     fmt.Println(list1)
    55.     list2 := []int{5, 9, 1}
    56.     QuickSort(list2, 0, len(list2)-1)
    57.     fmt.Println(list2)
    59.     list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
    60.     QuickSort(list3, 0, len(list3)-1)
    61.     fmt.Println(list3)
    62. }

    输出：

    1. [5]
    2. [5 9]
    3. [1 5 9]
    4. [1 3 4 5 6 6 6 8 9 14 25 49]

    示例图：

    快速排序，每一次切分都维护两个下标，进行推进，最后将数列分成两部分。

    快速排序可以继续进行算法改进。

    1. 在小规模数组的情况下，直接插入排序的效率最好，当快速排序递归部分进入小数组范围，可以切换成直接插入排序。
    2. 排序数列可能存在大量重复值，使用三向切分快速排序，将数组分成三部分，大于基准数，等于基准数，小于基准数，这个时候需要维护三个下标。
    3. 使用伪尾递归减少程序栈空间占用，使得栈空间复杂度从 O(logn) ~ log(n) 变为：O(logn)。

    3.1 改进：小规模数组使用直接插入排序

    在小规模数组的情况下，直接插入排序的效率最好，当快速排序递归部分进入小数组范围，可以切换成直接插入排序。

    直接插入排序在小规模数组下效率极好，我们只需将 end-begin <= 4 的递归部分换成直接插入排序，这部分表示小数组排序。

    排序数列可能存在大量重复值，使用三向切分快速排序，将数组分成三部分，大于基准数，等于基准数，小于基准数，这个时候需要维护三个下标。

    1. package main
    3. import "fmt"
    5. // QuickSort2 三切分的快速排序
    6. func QuickSort2(array []int, begin, end int) {
    7.     if begin < end {
    8.         // 三向切分函数，返回左边和右边下标
    9.         lt, gt := partition3(array, begin, end)
    10.         // 从lt到gt的部分是三切分的中间数列
    11.         // 左边三向快排
    12.         QuickSort2(array, begin, lt-1)
    13.         // 右边三向快排
    14.         QuickSort2(array, gt+1, end)
    15.     }
    16. }
    18. // 切分函数，并返回切分元素的下标
    19. func partition3(array []int, begin, end int) (int, int) {
    20.     lt := begin       // 左下标从第一位开始
    21.     gt := end         // 右下标是数组的最后一位
    22.     i := begin + 1    // 中间下标，从第二位开始
    23.     v := array[begin] // 基准数
    25.     // 以中间坐标为准
    26.     for i <= gt {
    27.         if array[i] > v { // 大于基准数，那么交换，右指针左移
    28.             array[i], array[gt] = array[gt], array[i]
    29.             gt--
    30.         } else if array[i] < v { // 小于基准数，那么交换，左指针右移
    31.             array[i], array[lt] = array[lt], array[i]
    32.             lt++
    33.             i++
    34.         } else {
    35.             i++
    36.         }
    37.     }
    39.     return lt, gt
    40. }

    演示：

    1. 数列：4 8 2 4 4 4 7 9，基准数为 4
    3. [4] [8] 2 4 4 4 7 [9]  从中间[]开始：8 > 4，中右[]进行交换，右边[]左移
    4. [4] [9] 2 4 4 4 [7] 8  从中间[]开始：9 > 4，中右[]进行交换，右边[]左移
    5. [4] [7] 2 4 4 [4] 9 8  从中间[]开始：7 > 4，中右[]进行交换，右边[]左移
    6. [4] [4] 2 4 [4] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移
    7. [4] 4 [2] 4 [4] 7 9 8  从中间[]开始：2 < 4，中左[]需要交换，中间和左边[]右移
    8. 2 [4] 4 [4] [4] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移
    9. 2 [4] 4 4 [[4]] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移，因为已经重叠了
    10. 第一轮结果：2 4 4 4 4 7 9 8
    12. 分成三个数列：
    14. 2
    15. 4 4 4 4 (元素相同的会聚集在中间数列)
    16. 7 9 8
    18. 接着对第一个和最后一个数列进行递归即可。

    示例图：

    快速排序 - 图3

    三切分，把小于基准数的扔到左边，大于基准数的扔到右边，相同的元素会进行聚集。

    如果存在大量重复元素，排序速度将极大提高，将会是线性时间，因为相同的元素将会聚集在中间，这些元素不再进入下一个递归迭代。

    三向切分主要来自荷兰国旗三色问题，该问题由 Dijkstra 提出。

    假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

    可以看到，上面的解答相当于使用三向切分一次，只要我们将白色旗子的值设置为 100，蓝色的旗子值设置为 0，红色旗子值设置为 200，以 100 作为基准数，第一次三向切分后三种颜色的旗就排好了，因为 蓝(0)白(100)红(200)。

    注：艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日)，荷兰人，计算机科学家，曾获图灵奖。

    3.3 改进：伪尾递归优化

    使用伪尾递归减少程序栈空间占用，使得栈空间复杂度从 O(logn) ~ log(n) 变为：O(logn)。

    1. // 伪尾递归快速排序
    2. func QuickSort3(array []int, begin, end int) {
    3.     for begin < end {
    4.         // 进行切分
    5.         loc := partition(array, begin, end)
    7.         // 那边元素少先排哪边
    8.         if loc-begin < end-loc {
    9.             // 先排左边
    10.             begin = loc + 1
    11.         } else {
    12.             // 先排右边
    13.             QuickSort3(array, loc+1, end)
    14.             end = loc - 1
    16.     }
    17. }

    很多人以为这样子是尾递归。其实这样的快排写法是伪装的尾递归，不是真正的尾递归，因为有 for 循环，不是直接 return QuickSort，递归还是不断地压栈，栈的层次仍然不断地增长。

    但是，因为先让规模小的部分排序，栈的深度大大减少，程序栈最深不会超过 logn 层，这样堆栈最坏空间复杂度从 O(n) 降为 O(logn)。

    这种优化也是一种很好的优化，因为栈的层数减少了，对于排序十亿个整数，也只要：log(100 0000 0000)=29.897，占用的堆栈层数最多 30 层，比不进行优化，可能出现的 O(n) 常数层好很多。

    四、补充：非递归写法

    1. // 非递归快速排序
    2. func QuickSort5(array []int) {
    4.     // 人工栈
    5.     helpStack := new(LinkStack)
    7.     // 第一次初始化栈，推入下标0，len(array)-1，表示第一次对全数组范围切分
    8.     helpStack.Push(len(array) - 1)
    9.     helpStack.Push(0)
    11.     // 栈非空证明存在未排序的部分
    12.     for !helpStack.IsEmpty() {
    13.         // 出栈，对begin-end范围进行切分排序
    14.         begin := helpStack.Pop() // 范围区间左边
    15.         end := helpStack.Pop()   // 范围
    17.         // 进行切分
    18.         loc := partition(array, begin, end)
    20.         // 右边范围入栈
    21.         if loc+1 < end {
    22.             helpStack.Push(end)
    23.             helpStack.Push(loc + 1)
    24.         }
    26.         // 左边返回入栈
    27.         if begin < loc-1 {
    28.             helpStack.Push(loc - 1)
    29.             helpStack.Push(begin)
    30.         }
    31.     }
    32. }

    本来需要进行递归的数组范围 begin,end，不使用递归，依次推入自己的人工栈，然后循环对人工栈进行处理。

    我们可以看到没有递归，程序栈空间复杂度变为了：O(1)，但额外的存储空间产生了。

    辅助人工栈结构 helpStack 占用了额外的空间，存储空间由原地排序的 O(1) 变成了 O(logn) ~ log(n)。

    我们可以参考上面的伪尾递归版本，继续优化非递归版本，先让短一点的范围入栈，这样存储复杂度可以变为：O(logn)。如：

    完整的程序如下：

    1. package main
    3. import (
    4.     "fmt"
    5.     "sync"
    6. )
    8. // LinkStack 链表栈，后进先出
    9. type LinkStack struct {
    10.     root *LinkNode  // 链表起点
    11.     size int        // 栈的元素数量
    12.     lock sync.Mutex // 为了并发安全使用的锁
    13. }
    15. // LinkNode 链表节点
    16. type LinkNode struct {
    17.     Next  *LinkNode
    18.     Value int
    19. }
    21. // Push 入栈
    22. func (stack *LinkStack) Push(v int) {
    23.     stack.lock.Lock()
    24.     defer stack.lock.Unlock()
    26.     // 如果栈顶为空，那么增加节点
    27.     if stack.root == nil {
    28.         stack.root = new(LinkNode)
    29.         stack.root.Value = v
    30.     } else {
    31.         // 否则新元素插入链表的头部
    32.         // 原来的链表
    33.         preNode := stack.root
    35.         // 新节点
    36.         newNode := new(LinkNode)
    37.         newNode.Value = v
    39.         // 原来的链表链接到新元素后面
    40.         newNode.Next = preNode
    42.         // 将新节点放在头部
    43.         stack.root = newNode
    44.     }
    46.     // 栈中元素数量+1
    47.     stack.size = stack.size + 1
    48. }
    50. // Pop 出栈
    51. func (stack *LinkStack) Pop() int {
    52.     stack.lock.Lock()
    53.     defer stack.lock.Unlock()
    55.     // 栈中元素已空
    56.     if stack.size == 0 {
    57.         panic("empty")
    58.     }
    60.     // 顶部元素要出栈
    61.     topNode := stack.root
    62.     v := topNode.Value
    64.     // 将顶部元素的后继链接链上
    65.     stack.root = topNode.Next
    67.     // 栈中元素数量-1
    68.     stack.size = stack.size - 1
    70.     return v
    71. }
    73. // IsEmpty 栈是否为空
    74. func (stack *LinkStack) IsEmpty() bool {
    75.     return stack.size == 0
    76. }
    78. // QuickSort5 非递归快速排序
    79. func QuickSort5(array []int) {
    81.     // 人工栈
    82.     helpStack := new(LinkStack)
    84.     // 第一次初始化栈，推入下标0，len(array)-1，表示第一次对全数组范围切分
    85.     helpStack.Push(len(array) - 1)
    86.     helpStack.Push(0)
    88.     // 栈非空证明存在未排序的部分
    89.     for !helpStack.IsEmpty() {
    90.         // 出栈，对begin-end范围进行切分排序
    91.         begin := helpStack.Pop() // 范围区间左边
    92.         end := helpStack.Pop()   // 范围
    94.         // 进行切分
    95.         loc := partition(array, begin, end)
    97.         // 右边范围入栈
    98.         if loc+1 < end {
    99.             helpStack.Push(end)
    100.             helpStack.Push(loc + 1)
    101.         }
    103.         // 左边返回入栈
    104.         if begin < loc-1 {
    105.             helpStack.Push(loc - 1)
    106.             helpStack.Push(begin)
    107.         }
    108.     }
    109. }
    111. // QuickSort6 非递归快速排序优化
    112. func QuickSort6(array []int) {
    114.     // 人工栈
    115.     helpStack := new(LinkStack)
    117.     // 第一次初始化栈，推入下标0，len(array)-1，表示第一次对全数组范围切分
    118.     helpStack.Push(len(array) - 1)
    119.     helpStack.Push(0)
    121.     // 栈非空证明存在未排序的部分
    122.     for !helpStack.IsEmpty() {
    123.         // 出栈，对begin-end范围进行切分排序
    124.         begin := helpStack.Pop() // 范围区间左边
    125.         end := helpStack.Pop()   // 范围
    127.         // 进行切分
    128.         loc := partition(array, begin, end)
    130.         // 切分后右边范围大小
    131.         rSize := -1
    132.         // 切分后左边范围大小
    133.         lSize := -1
    135.         // 右边范围入栈
    136.         if loc+1 < end {
    137.             rSize = end - (loc + 1)
    138.         }
    140.         // 左边返回入栈
    141.         if begin < loc-1 {
    142.             lSize = loc - 1 - begin
    143.         }
    145.         // 两个范围，让范围小的先入栈，减少人工栈空间
    146.         if rSize != -1 && lSize != -1 {
    147.             if lSize > rSize {
    148.                 helpStack.Push(end)
    149.                 helpStack.Push(loc + 1)
    150.                 helpStack.Push(loc - 1)
    151.                 helpStack.Push(begin)
    152.             } else {
    153.                 helpStack.Push(loc - 1)
    154.                 helpStack.Push(begin)
    155.                 helpStack.Push(end)
    156.                 helpStack.Push(loc + 1)
    157.             }
    158.         } else {
    159.                 helpStack.Push(end)
    160.                 helpStack.Push(loc + 1)
    161.             }
    163.             if lSize != -1 {
    164.                 helpStack.Push(loc - 1)
    165.                 helpStack.Push(begin)
    166.             }
    167.         }
    168.     }
    169. }
    171. // 切分函数，并返回切分元素的下标
    172. func partition(array []int, begin, end int) int {
    173.     i := begin + 1 // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
    174.     j := end       // array[end]是数组的最后一位
    176.     // 没重合之前
    177.     for i < j {
    178.         if array[i] > array[begin] {
    179.             array[i], array[j] = array[j], array[i] // 交换
    180.             j--
    181.         } else {
    182.             i++
    183.         }
    184.     }
    186.     /* 跳出 for 循环后，i = j。
    187.      * 此时数组被分割成两个部分   -->  array[begin+1] ~ array[i-1] < array[begin]
    188.      *                        -->  array[i+1] ~ array[end] > array[begin]
    189.      * 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。
    190.      * 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！
    191.      */
    192.     if array[i] >= array[begin] { // 这里必须要取等“>=”，否则数组元素由相同的值组成时，会出现错误！
    193.         i--
    194.     }
    196.     array[begin], array[i] = array[i], array[begin]
    197.     return i
    198. }
    200. func main() {
    201.     list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
    202.     QuickSort5(list3)
    203.     fmt.Println(list3)
    205.     list4 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
    206.     QuickSort6(list4)
    207.     fmt.Println(list4)
    208. }

    输出：

    1. [1 3 4 5 6 6 6 8 9 14 25 49]
    2. [1 3 4 5 6 6 6 8 9 14 25 49]

    使用人工栈替代递归的程序栈，换汤不换药，速度并没有什么变化，但是代码可读性降低。

    首先堆排序，归并排序最好最坏时间复杂度都是：O(nlogn)，而快速排序最坏的时间复杂度是：O(n^2)，但是很多编程语言内置的排序算法使用的仍然是快速排序，这是为什么？

    1. 这个问题有偏颇，选择排序算法要看具体的场景，Linux 内核用的排序算法就是堆排序，而 Java 对于数量比较多的复杂对象排序，内置排序使用的是归并排序，只是一般情况下，快速排序更快。
    2. 归并排序有两个稳定，第一个稳定是排序前后相同的元素位置不变，第二个稳定是，每次都是很平均地进行排序，读取数据也是顺序读取，能够利用存储器缓存的特征，比如从磁盘读取数据进行排序。因为排序过程需要占用额外的辅助数组空间，所以这部分有代价损耗，但是原地手摇的归并排序克服了这个缺陷。
    3. 复杂度中，大 O 有一个常数项被省略了，堆排序每次取最大的值之后，都需要进行节点翻转，重新恢复堆的特征，做了大量无用功，常数项比快速排序大，大部分情况下比快速排序慢很多。但是堆排序时间较稳定，不会出现快排最坏 O(n^2) 的情况，且省空间，不需要额外的存储空间和栈空间。
    4. 当待排序数量大于16000个元素时，使用自底向上的堆排序比快速排序还快，可见此：。
    5. 快速排序最坏情况下复杂度高，主要在于切分不像归并排序一样平均，而是很依赖基准数的现在，我们通过改进，比如随机数，三切分等，这种最坏情况的概率极大的降低。大多数情况下，它并不会那么地坏，大多数快才是真的块。
    6. 归并排序和快速排序都是分治法，排序的数据都是相邻的，而堆排序比较的数可能跨越很大的范围，导致局部性命中率降低，不能利用现代存储器缓存的特征，加载数据过程会损失性能。

    对稳定性有要求的，要求排序前后相同元素位置不变，可以使用归并排序，Java 中的复杂对象类型，要求排序前后位置不能发生变化，所以小规模数据下使用了直接插入排序，大规模数据下使用了归并排序。

    对栈，存储空间有要求的可以使用堆排序，比如 Linux 内核栈小，快速排序占用程序栈太大了，使用快速排序可能栈溢出，所以使用了堆排序。

    六、补充：Golang 内置排序库 sort

    在 Golang 中，标准库 sort 中使用了多种排序算法，值得研究。

    例子：

    1. package main
    3. import (
    4.     "fmt"
    5.     "sort"
    6. )
    8. func InnerSort() {
    9.     list := []struct {
    10.         Name string
    11.         Age  int
    12.     }{
    13.         {"A", 75},
    14.         {"B", 4},
    15.         {"C", 5},
    16.         {"D", 5},
    17.         {"E", 2},
    18.         {"F", 5},
    19.         {"G", 5},
    20.     }
    22.     sort.SliceStable(list, func(i, j int) bool { return list[i].Age < list[j].Age })
    23.     fmt.Println(list)
    25.     list2 := []struct {
    26.         Name string
    27.         Age  int
    28.     }{
    29.         {"A", 75},
    30.         {"B", 4},
    31.         {"C", 5},
    32.         {"D", 5},
    33.         {"E", 2},
    34.         {"F", 5},
    35.         {"G", 5},
    36.     }
    38.     sort.Slice(list2, func(i, j int) bool { return list2[i].Age < list2[j].Age })
    39.     fmt.Println(list2)
    40. }
    42. func main() {
    43.     InnerSort()
    44. }

    输出：

    1. [{E 2} {B 4} {C 5} {D 5} {F 5} {G 5} {A 75}]
    2. [{E 2} {B 4} {G 5} {C 5} {D 5} {F 5} {A 75}]

    其中 SliceStable 是稳定排序，使用了插入排序和归并排序：

    会先按照 20 个元素的范围，对整个切片分段进行插入排序，因为小数组插入排序效率高。然后再对这些已排好序的小数组进行归并排序。其中归并排序还使用了原地排序，节约了辅助空间。

    而 Slice 是一般的排序，不追求稳定排序，使用了快速排序:

    1. func Slice(slice interface{}, less func(i, j int) bool) {
    2.     rv := reflectValueOf(slice)
    3.     swap := reflectSwapper(slice)
    4.     length := rv.Len()
    5.     quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
    6. }
    8. func quickSort_func(data lessSwap, a, b, maxDepth int) {
    9.     for b-a > 12 {
    10.         if maxDepth == 0 {
    11.             heapSort_func(data, a, b)
    12.             return
    13.         }
    14.         maxDepth--
    15.         mlo, mhi := doPivot_func(data, a, b)
    16.         if mlo-a < b-mhi {
    17.             quickSort_func(data, a, mlo, maxDepth)
    18.             a = mhi
    19.         } else {
    20.             quickSort_func(data, mhi, b, maxDepth)
    21.             b = mlo
    22.         }
    23.     }
    24.     if b-a > 1 {
    25.         for i := a + 6; i < b; i++ {
    26.             if data.Less(i, i-6) {
    27.                 data.Swap(i, i-6)
    28.             }
    29.         }
    30.         insertionSort_func(data, a, b)
    31.     }
    32. }
    34. func doPivot_func(data lessSwap, lo, hi int) (midlo, midhi int) {
    35.     m := int(uint(lo+hi) >> 1)
    36.     if hi-lo > 40 {
    37.         s := (hi - lo) / 8
    38.         medianOfThree_func(data, lo, lo+s, lo+2*s)
    39.         medianOfThree_func(data, m, m-s, m+s)
    40.         medianOfThree_func(data, hi-1, hi-1-s, hi-1-2*s)
    41.     }
    42.     medianOfThree_func(data, lo, m, hi-1)
    43.     pivot := lo
    44.     a, c := lo+1, hi-1
    45.     for ; a < c && data.Less(a, pivot); a++ {
    46.     }
    47.     b := a
    48.     for {
    49.         for ; b < c && !data.Less(pivot, b); b++ {
    50.         }
    51.         for ; b < c && data.Less(pivot, c-1); c-- {
    52.         }
    53.         if b >= c {
    54.             break
    55.         }
    56.         data.Swap(b, c-1)
    57.         b++
    58.         c--
    59.     }
    60.     protect := hi-c < 5
    61.     if !protect && hi-c < (hi-lo)/4 {
    62.         dups := 0
    63.         if !data.Less(pivot, hi-1) {
    64.             data.Swap(c, hi-1)
    65.             c++
    66.             dups++
    67.         }
    68.         if !data.Less(b-1, pivot) {
    69.             b--
    70.             dups++
    71.         }
    72.         if !data.Less(m, pivot) {
    73.             data.Swap(m, b-1)
    74.             b--
    75.             dups++
    76.         }
    77.         protect = dups > 1
    78.     }
    79.     if protect {
    80.         for {
    81.             for ; a < b && !data.Less(b-1, pivot); b-- {
    82.             }
    83.             for ; a < b && data.Less(a, pivot); a++ {
    84.             }
    85.             if a >= b {
    86.                 break
    87.             }
    88.             data.Swap(a, b-1)
    89.             a++
    90.             b--
    91.         }
    92.     }
    93.     data.Swap(pivot, b-1)
    94.     return b - 1, c

    快速排序限制程序栈的层数为： ，当递归超过该层时表示程序栈过深，内部会转为堆排序。

    上述快速排序还使用了三种优化，第一种是递归时小数组转为插入排序，第二种是使用了中位数基准数，第三种使用了三向切分。

    代码下载： https://github.com/hunterhug/goa.c/tree/master/code/sort/quicksort 。