关于数据结构与算法:常用排序算法之快速排序

疾速排序（Quick Sort）

疾速排序，又称分区替换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在均匀情况下，排序 n 个我的项目要 O(n\log n) 次比拟。在最坏情况下则须要 O(n^2) 次比拟。（inner loop）能够在大部分的架构上很有效率地达成。

疾速排序应用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的 2 个子序列，而后递归地排序两个子序列。步骤为：

• 筛选基准值：从数列中挑出一个元素，称为“基准”（pivot），
• 宰割：从新排序数列，所有比基准值小的元素摆放在基准后面，所有比基准值大的元素摆在基准前面（与基准值相等的数能够到任何一边）。在这个宰割完结之后，对基准值的排序就曾经实现，
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

贴上一份手写 golang 代码参考：

package main

import ("fmt")

func main() {s := []int {9, 8, 7, 6, 5, 4, 3, 2, 1}
    res := quickSort(s)
    fmt.Println(res)
}

func quickSort(values []int) []int {if len(values) <= 1 {return values}

    middle := values[0]
    left := make([]int, 0, 10)
    right := make([]int, 0, 10)

    for i := 1; i < len(values); i++ {if middle <= values[i] {right = append(right, values[i])
        } else {left = append(left, values[i])
        }
    }

    left = quickSort(left)
    right = quickSort(right)

    return append(left, append([]int {middle}, right...)...)
}