Quick Sort

快速排序是一种常用的内部排序算法，平均时间复杂度为 O(nlogn)。

算法思路

快速排序使用分治法来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。步骤如下：

挑选基准值: 从序列中选择任意一个元素作为基准，通常选择序列的第一个元素。
分割序列: 将序列中比基准元素小的元素放到基准前面，大的放在基准后面。
递归排序: 对较小的和较大的子序列分别进行上述操作。

举例说明

例如对序列 [ 3, 5, 4, 1, 2, 6 ] 进行快速排序

选取元素 3 作为基准元素。
将比 3 小的元素放在 3 前面，大的放在 3 后面，将其分割成两个子序列。
重复上述两个步骤，直到子序列划分完毕。

划分序列

序列划分有两种常用的方式。

方法一

从左到右遍历并调整交换位置，用offset记录偏移的量，用于填充基准元素。

初始化 offset 基准元素后的第一个位置 ( 即offset = low + 1 )，从offset位置开始往后扫描，找到比 3 小的元素 1，交换 1 和基准外第一个位置的元素 5，交换后offset自增。
找到比 3 小的元素 2，交换 2 和基准外第二个位置的元素 4，交换后offset自增。
将基准元素与 offset - 1 位置处元素交换位置，既可将序列划分成两部分。

方法二

从两端向中间遍历，用变量缓存基准元素。

将序列第一个元素 2 当做基准元素，定义 pivot 变量缓存基准元素的值，并使 low 和 high 分别赋值为第一个元素和最后一个元素的索引。
从后往前找到第一个比基准元素小的元素 2，将其赋值给 s[low]。
从前往前后到第一个比基准元素大的元素 5，将其赋值给 s[high]。
从后往前找到第一个比基准元素小的元素 1，将其赋值给 s[low]。
从前往前后到第一个比基准元素大的元素 4，将其赋值给 s[high]。
到达终止条件，将 pivot 赋值给 s[low]，即可将序列划分成两部分。

具体实现

分割序列，递归划分子序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func Sort(s []int, low, high int) {
    if low < high {
        // 分割序列，返回基准元素索引
        pivot := partition(s, low, high)
        // 递归分割左侧
        Sort(s, low, pivot-1)
        // 递归分割右侧
        Sort(s, pivot+1, high)
    }
}

方法一

第一种分割方式实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func partition(s []int, low, high int) int {
    pivot := low
    offset := pivot + 1

    // 从前往后寻找
    for i := offset; i <= high; i++ {
        if s[i] < s[pivot] {
            s[i], s[offset] = s[offset], s[i]
            offset++
        }
    }
    s[pivot], s[offset-1] = s[offset-1], s[pivot]

    return offset - 1
}

方法二

第二种分割方式实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func partition(s []int, low, high int) int {
    pivot := s[low]

    for low < high {
        // 从后往前找比基准元素小的元素的索引
        for low < high && s[high] >= pivot {
            high--
        }
        s[low] = s[high]

        // 从前往后找比基准元素小的元素的索引
        for low < high && s[low] <= pivot {
            low ++
        }
        s[high] = s[low]
    }
    // 将基准元素插入两个子序列中间
    s[low] = pivot

    return low
}

单元测试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


package quicksort

import "testing"

func TestSort(t *testing.T) {
    testCase := []struct {
        input    []int
        expected []int
    }{
        {[]int{3}, []int{3}},
        {[]int{2, 1}, []int{1, 2}},
        {[]int{1, 3, 1, 2}, []int{1, 1, 2, 3}},
        {[]int{3, 1, 4, 2}, []int{1, 2, 3, 4}},
    }

    for _, c := range testCase {
        res := Sort(c.input, 0, len(c.input)-1)
        if !equal(res, c.expected) {
            t.Fatalf("values = %v, expected %v", res, c.expected)
        }
    }
}

func equal(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }

    for idx := 0; idx < len(a); idx++ {
        if a[idx] != a[idx] {
            return false
        }
    }

    return true
}