排序算法

Posted on Edited on In Views:
在日常工作中很多时候我们会用到排序算法，这里将常用的排序算法做一个归纳。

sort包

golang中自带的排序可以通过sort包实现，例如排序int切片

1
2
3
s := []int{2, 4, 6, 7, 9, 8, 5, 3, 1}
sort.Ints(s)
fmt.Println(s)

除了int，还可以排序string，而且sort包提供接口，当自定义类型实现了接口，则可以通过sort方法排序

1
2
3
4
5
type Interface interface {
    Len() int								// 集合中元素的数量
    Less(i, j int) bool			// 函数判断下标i的元素是否应该放在下标j的前面
    Swap(i, j int)					// 函数交换下标i、j对应的元素
}

例如排序结构体

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
37
38
39
40
41
42
43
44
type Student struct {
    Name  string
    Age   int
    Score int
}

type Students []Student

func (s Students) Len() int {
    return len(s)
}

func (s Students) Less(i, j int) bool {
    // return s[i].Age < s[j].Age         // 按照年龄正序
    return s[i].Score > s[j].Score				// 将分数大的往前排，按照分数排序
}
func (s Students) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    s := Students{
        Student{
            Name:  "a",
            Age:   17,
            Score: 90,
        }, Student{
            Name:  "b",
            Age:   18,
            Score: 80,
        }, Student{
            Name:  "c",
            Age:   18,
            Score: 95,
        },
        Student{
            Name:  "d",
            Age:   18,
            Score: 85,
        },
    }
    sort.Sort(s)
    fmt.Println(s)
}

通过查看sort源码可以看到，排序方式是快排，而且是不稳定的排序算法。

不稳定排序算法指的是不保证排序后相同大小元素的原始次序不变的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Sort按Less方法确定的升序对数据进行排序。它对数据进行一次调用。
// Len来确定对数据的n和O（n*log（n））调用Less和Swap。排序不能保证是稳定的。
func Sort(data Interface) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

// maxDepth返回一个阈值，在该阈值下，快速排序应切换到堆排序。它返回2*ceil（lg（n+1））。
// 也就是返回要排序的个数组成二叉树之后的深度 * 2 
func maxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return depth * 2
}

堆排序

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
37
38
39
40
41
42
43
44
45
46
47
// siftDown implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
// 在data[lo:hi]上实现了堆属性。first是堆根所在的数组的偏移量。
func siftDown(data Interface, lo, hi, first int) {
    root := lo
    for {
        // 左孩子下标
        child := 2*root + 1
        // 超出切片，则break
        if child >= hi {
            break
        }
        // child+1就是右孩子节点
        // 不停的移动child值，让child位置的值最大
        if child+1 < hi && data.Less(first+child, first+child+1) {
            child++
        }
        // 如果root位置的值就是最大值，则直接返回
        if !data.Less(first+root, first+child) {
            return
        }
        // 交换root值和孩子值，让root的值保持最大
        data.Swap(first+root, first+child)
        root = child
    }
}

// 堆排序
func heapSort(data Interface, a, b int) {
    first := a
    lo := 0
    hi := b - a

    // Build heapheap with greatest element at top.
    // 构建最大数在顶端的堆
    for i := (hi - 1) / 2; i >= 0; i-- {
        siftDown(data, i, hi, first)
    }

    // Pop elements, largest first, into end of data.
    // 丢出元素，先丢出最大元素，放在切片末尾
    // 并且维护堆属性，继续选出最大堆
    for i := hi - 1; i >= 0; i-- {
        data.Swap(first, first+i)
        siftDown(data, lo, i, first)
    }
}

插入排序

1
2
3
4
5
6
7
8
9
// insertionSort sorts data[a:b] using insertion sort.
// 插入排序，将后面的数，小于前面的数时，进行调换
func insertionSort(data Interface, a, b int) {
    for i := a + 1; i < b; i++ {
        for j := i; j > a && data.Less(j, j-1); j-- {
            data.Swap(j, j-1)
        }
    }
}

通过支点切分数组

先取支点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 将数组中的三个角标的数字中的中间大小的数移动到中间，也就是选择一个不是最大也不是最小的数作为支点，放在首位。
// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func medianOfThree(data Interface, m1, m0, m2 int) {
    // sort 3 elements
    if data.Less(m1, m0) {
        data.Swap(m1, m0)
    }
    // data[m0] <= data[m1]
    if data.Less(m2, m1) {
        data.Swap(m2, m1)
        // data[m0] <= data[m2] && data[m1] < data[m2]
        if data.Less(m1, m0) {
            data.Swap(m1, m0)
        }
    }
    // now data[m0] <= data[m1] <= data[m2]
}

然后切分

把不小于 data[pivot] 的数据放在了 [lo, b) 区间，把大于 data[pivot] 的数据放在了 (c, hi-1] 区间（其中 data[hi-1] >= data[pivot]）。

之后，该算法又估算了等于 data[pivot] 的数量，如果数量过多，则把与 data[pivot] 相等的数据放到了中间部分 区间为(b, c-1)。最后把 data[pivot] 交换到了 b-1 的位置。

至此，数据被切分成三个区间。
data[lo, b-1)
data[b-1, c)
data[c, hi)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// doPivot 切分切片，切成两个等分，并且第一等分中的数字都小于第二等分
// 影响快排的速度就是这个支点的位置，如果支点位置好，则区分就快
func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    // 取平均数，避免整数溢出（int最大数小于uint最大数，int有一位存储符号）
    m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
    // 取元素中的头、中、尾三个位置的元素的中值元素移动到中间位置
    // 当元素个数大于40，则将数据分为三个部分，分别将三个部分的三元素中中值元素移动到中间位置
    if hi-lo > 40 {
        // Tukey's ``Ninther,'' median of three medians of three.
        s := (hi - lo) / 8
        medianOfThree(data, lo, lo+s, lo+2*s)
        medianOfThree(data, m, m-s, m+s)
        medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    }
    medianOfThree(data, lo, m, hi-1)
    // 现在变成 data[lo] <= data[m] <= data[hi-1]

    // Invariants are:
    //	data[lo] = pivot (set up by ChoosePivot)
    //	data[lo < i < a] < pivot
    //	data[a <= i < b] <= pivot
    //	data[b <= i < c] unexamined
    //	data[c <= i < hi-1] > pivot
    //	data[hi-1] >= pivot
    // 选择起始位置作为支点
    pivot := lo
    a, c := lo+1, hi-1

    // 下面的逻辑是使用支点排序，小于支点的往前移动，大于支点的往后移动
    // 找到第一个大于支点的角标
    for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
        // 找到 大于支点之后 又小于支点的角标
        for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
        // 从后往前，找到大于支点的角标
        for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
        if b >= c {
            break
        }
        // 交换两个角标，
        // data[b] > pivot; data[c-1] <= pivot
        data.Swap(b, c-1)
        b++
        c--
    }
    // 检测是否有重复元素，如果有重复元素，
    // If hi-c<3 then there are duplicates (by property of median of nine).
    // Let's be a bit more conservative, and set border to 5.
    protect := hi-c < 5
    if !protect && hi-c < (hi-lo)/4 {
        // Lets test some points for equality to pivot
        // 检查与支点重复的元素个数
        dups := 0
        if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
            data.Swap(c, hi-1)
            c++
            dups++
        }
        if !data.Less(b-1, pivot) { // data[b-1] = pivot
            b--
            dups++
        }
        // m-lo = (hi-lo)/2 > 6
        // b-lo > (hi-lo)*3/4-1 > 8
        // ==> m < b ==> data[m] <= pivot
        if !data.Less(m, pivot) { // data[m] = pivot
            data.Swap(m, b-1)
            b--
            dups++
        }
        // if at least 2 points are equal to pivot, assume skewed distribution
        protect = dups > 1
    }
    if protect {
        // Protect against a lot of duplicates
        // Add invariant:
        //	data[a <= i < b] unexamined
        //	data[b <= i < c] = pivot
        for {
            for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
            for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
            if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot
            data.Swap(a, b-1)
            a++
            b--
        }
    }
    // Swap pivot into middle
    data.Swap(pivot, b-1)
    return b - 1, c
}

快排

快排的核心是切分数组到小的数组，然后使用其他的排序算法将小数组排序，再最终组合成一整个数组。

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
// 快速排序（核心逻辑并不完全是快排）
func quickSort(data Interface, a, b, maxDepth int) {
  // 当元素个数大于12个时，使用快排
    for b-a > 12 { 
        if maxDepth == 0 {  // 深度为0，使用堆排序
            heapSort(data, a, b)
            return
        }
        maxDepth--
    // 当元素大于12个，将元素拆开成2个部分，将大问题划分为小问题
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
  // Use ShellSort for slices <= 12 elements   当元素小于12个时，使用希尔排序
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
    // 在元素个数小于12时，希尔排序可以简化成这个样子
    // 插入排序之前，先间隔六个的数字比较一下
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
    // 使用插入排序
        insertionSort(data, a, b)
    }
}

扩展其他的排序方法

冒泡排序

冒泡排序的思想是比较相邻的两个数字，然后将这两个数字排序。

1
2
3
if rand[j] > rand[j+1] {
    rand[j], rand[j+1] = rand[j+1], rand[j]
}

具体代码实现

1
2
3
4
5
6
7
for i := 0; i < len(rand)-1; i++ {
    for j := 0; j < len(rand)-1-i; j++ {
        if rand[j] > rand[j+1] {
            rand[j], rand[j+1] = rand[j+1], rand[j]
        }
    }
}

冒泡排序所需的时间是n+n-1+...1，如果不加条件判断，即使排序好了也再次排序，时间复杂度是n^2。

快速排序中的递归思想

快速排序的思想是随机选择一个数，将这个数与其他的数比较，将小于这个数放到一边，将大于这个数放到一边，分两边之后再次按照上述过程排序。快速排序的时间复杂度依赖随机选的这个数，所以时间复杂度是不稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if len(s) <= 1 {
    return s
}
left := make([]int, 0)
right := make([]int, 0)
mid := make([]int, 0)
res := make([]int, 0)
flag := s[0]
mid = append(mid, flag)
for _, v := range s {
    if v > flag {
        right = append(right, v)
    } else if v < flag {
        left = append(left, v)
    }
}
left, right = kuaipai(left), kuaipai(right)
res = append(append(left, mid...), right...)
return res

最不好的时间复杂度是n^2，平均时间复杂度是nlogn