快速排序 Quick sort

快排利用的也是分治思想，也是把一串数据分为两个子串，但是与归并排序不同的是，分区点(pivot)是数组区间范围内的任意值。将两个子串的值分别与分区点的值进行比较，较小的值放到分区点左边，较大的值放到分区点的右边。这样，利用递归的思想，子串再进行任意拆分比较，最终将原始数据串进行有序排列。

算法步骤

1. 在数组区间内选任意值为分区点(pivot)，一般使用序列的第一个值作为下一个分区点。
2. 重新排列数据，比分区点值小的放到其前面，反之放到其后面。
3. 重复步骤2，直到子序列长度为1
4. 总结成递归公式即为：

递推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
终止条件：p >= r

动画演示

性能分析

• 空间复杂度

任何情况下均为。

• 时间复杂度

• 稳定性

是一种原地、不稳定的排序算法

代码

func Quicksort(nums []int) {
    quickSorts(nums, 0, len(nums)-1)
}

func quickSorts(nums []int, head, tail int) {
    if head >= tail {
        return
    }
    // 指定区间内获取分区点索引
    p := getPivot(nums, head, tail)
    quickSorts(nums, head, p-1)
    quickSorts(nums, p+1, tail)
}

func getPivot(nums []int, head, tail int) int {
    // 以数组头为分区点
    pivot := nums[head]
    pIndex := head + 1
    for i := head + 1; i <= tail; i++ {
        if nums[i] < pivot {
            // 比分区点的值小，则放到分区点左侧
            nums[i], nums[pIndex] = nums[pIndex], nums[i]
            pIndex++
        }
    }
    nums[pIndex-1], nums[head] = nums[head], nums[pIndex-1]
    return pIndex - 1
}