Sort排序总结

Posted on | Edited on | In

最近在复习算法。翻出小伙伴在14年写的排序算法开始读，发现自己离开C/C++已经太久到打分号都很不习惯，于是乎打算写个go的堆排快排总结，主要根据标准库的sort包写的，另外刷了几道LeetCode的题目。

Sort Interface

sort的参数是个接口，它实现计算长度，比较以及Swap这三个方法。然后Sort方法根据深度来判断当前排序使用heapSort quickSort还是insertSort。实现这个接口是为了扩展sort支持自定义的数据结构的排序，比如在kubernetes中通过pod的createTimeStamp来排序处理Pod事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

func Sort(data Interface) {
    // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
    n := data.Len()
    maxDepth := 0
    for i := n; i > 0; i >>= 1 {
        maxDepth++
    }
    maxDepth *= 2
    quickSort(data, 0, n, maxDepth)
}

sort包给了Int Float String这三种类型的接口实现，go的swap可以平行赋值，编译器先计算右值再进行赋值。不需要显示的通过中间变量来存储，也不需要用异或运算等方法影响可读性。

1
2
3
4
5
6
7
type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

//sort.Sort(sort.IntSlice(data))

Insert Sort

在排序len大于1小于等于7时，sort包默认使用插入排序。插入排序的思路是对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  • 左边是有序区，右边是无序区，每次循环期望找到无序区的第一个data在有序区中的位置下标
  • 确认位置后，这之后的有序区元素依次右移。
  • 这个过程中找到位置和数据右移可以合并，例如下面的实现。
1
2
3
4
5
6
7
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)
        }
    }
}

HeapSort

堆排序，是利用大顶堆或小顶堆的相关操作完成的。大顶堆就是父节点的键值总是大于或等于任何一个子节点的键值；同时每个节点的左子树和右子树都是一个大顶堆。从小到大排序的基本思路是：

  • 构建大顶堆，保证root节点是最大的。
  • 数组末尾是有序区，每次循环保证将大顶堆的root节点置换到有序区。
  • 循环中对无序区的数据进行堆化，保证root节点是无序区中最大的。

堆化数据

堆化数据的一个点在于，以0为根节点的大顶堆，其第i个数据的子节点分别为2i+1和2i+2，这个很好证明，略。堆化数据从堆底开始，跳过所有叶子节点，起始显然是最后一个叶子节点n-1的父节点，位置是n-1-1/2。siftDown完成了从i到hi的数据堆化。

sort包里写的是(hi-1)/2，逻辑上漏掉了hi-1才是叶子节点的位置，但实际上不影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func heapSort(data Interface, a, b int) {
    first := a
    lo := 0
    hi := b - a

    // Build heap with greatest element at top.
    for i := hi/2 - 1; 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)
    }
}

siftDown数据堆化的思路是，从root节点开始，置换保证root节点是子节点中最大的，只所以这里能return，是因为堆排的时候是从下到上堆化的，所以下端都已经是大顶堆了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func siftDown(data Interface, lo, hi, first int) {
    root := lo
    for {
        child := 2*root + 1
        if child >= hi {
            break
        }
        if child+1 < hi && data.Less(first+child, first+child+1) {
            child++
        }
        if !data.Less(first+root, first+child) {
            return
        }
        data.Swap(first+root, first+child)
        root = child
    }
}

堆的删除

堆都是从data[0]的地方pop数据，在堆排中显然pop出去的当前无序区最大值将置换到data[n-1]，这时有序区终于有一个值了。然后无序区开始siftDown，堆化后继续pop扩大有序区直到完全有序。

过程示例 下图转自经典排序算法总结

heapsort实例

QuickSort

快排和归并都是分治的思路。go的快排通过maxDepth实现了对递归调用深度的限制，不超过lg(b-a)。另外数据len小于等于7时切到了插入排序。

深度的计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 7 {
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        maxDepth--
        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)
        }
    }
    if b-a > 1 {
        insertionSort(data, a, b)
    }
}

剪掉分支，单纯的快排go的sort包是这样实现的。快排的思路是标记一个基准数，将比这个数大的全放到右边，比他小的都放到左边，这是个不断挖坑填坑的过程。完成后，对左右分区做同样的事，直到各区只有一个数。sort包的快排过程思路类似，但稍有不同。

  • 在data中从左找比data[0]大的记录为b，从右找比data[0]小的记录为c，找到后swap(b, c)
  • 同时用变量a和d记录与data[0]相等的位置，并把与data[0]相等的数都swap到两端
  • 循环过后其实已经分好左边到b都比data[0]小，右边c之后都比data[0]大。这时开始swapRange就是将b位置的x个位置与data[0]起始的x个位置swap。
  • 最终的结果就是data[0]和与之相等的值都放到了正确位置。
1
2
3
4
5
6
7
func quickSort(data Interface, a, b int) {
    if a < b-1 {
        mlo, mhi := doPivot(data, a, b)
        quickSort(data, a, mlo)
        quickSort(data, mhi, b)
    }
}
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
func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    pivot := lo
    a, b, c, d := lo+1, lo+1, hi, hi
    for {
        for b < c {
            if data.Less(b, pivot) { // data[b] < pivot
                b++
            } else if !data.Less(pivot, b) { // data[b] = pivot
                data.Swap(a, b)
                a++
                b++
            } else {
                break
            }
        }
        for b < c {
            if data.Less(pivot, c-1) { // data[c-1] > pivot
                c--
            } else if !data.Less(c-1, pivot) { // data[c-1] = pivot
                data.Swap(c-1, d-1)
                c--
                d--
            } else {
                break
            }
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] < pivot
        data.Swap(b, c-1)
        b++
        c--
    }

    n := min(b-a, a-lo)
    swapRange(data, lo, b-n, n)

    n = min(hi-d, d-c)
    swapRange(data, c, hi-n, n)

    return lo + b - a, hi - (d - c)
}

重写一遍doPivot，思路清晰一点。当b位置被小于pivot的值覆盖后，c就是坑。之后c被大于pivot的值覆盖，最后坑就是b==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

func doPivot(a []int, lo int, hi int) int {
    pivot := a[lo]
    b, c := lo, hi
    for b < c {
        for b < c && a[c] >= pivot {
            c--
        }
        if b < c {
            a[b] = a[c]
            b++
        }

        for b < c && a[b] < pivot {
            b++
        }
        if b < c {
            a[c] = a[b]
        }
    }
    a[b] = pivot
    return b
}

func quickSort(a []int, low int, high int) {
    if low < high {
        var pivot = doPivot(a, low, high)
        quickSort(a, low, pivot-1)
        quickSort(a, pivot+1, high)
    }
}

MergeSort

归并排序sort包里没有，原理很简单，跟快排一样是分治。不过是靠合并两个有序数列为基础实现的，需要额外的空间存储合并结果。

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 MergeSort(data []int) {
    sp := make([]int, len(data))
    mergeSort(data, 0, len(data)-1, sp)
}
func mergeSort(data []int, first, last int, sp []int) {
    if first < last {
        mid := first + (last-first)/2
        mergeSort(data, first, mid, sp)
        mergeSort(data, mid+1, last, sp)
        merge(data, first, mid, last, sp)
    }
}

func merge(data []int, first, mid, last int, sp []int) {
    i, j, k := first, mid+1, 0
    for ; i <= mid && j <= last; k++ {
        if data[i] < data[j] {
            sp[k] = data[i]
            i++
        } else {
            sp[k] = data[j]
            j++
        }
    }
    for ; i <= mid; i++ {
        sp[k] = data[i]
        k++
    }
    for ; j <= last; j++ {
        sp[k] = data[j]
        k++
    }
    for i = 0; i < k; i++ {
        data[first+i] = sp[i]
    }
}

Summary

在数据较少，且可能整体有序的情况，可以考虑insertsort。最坏的情况下堆排和归并排序较好。所谓稳定排序是指里那个相等的元素排序之后二者的相对顺序是否不变。

快排可以实现稳定吗，为什么最坏情况下是O(n^2)，辅助空间怎样计算

Reference

经典排序算法总结

白话经典算法系列

排序问题