参考:

概念

首先, 排序是指, 将一个数组中的元素按照特定顺序放置, 并不一定是从小到大或者从大到小, 排序的最终目的, 很大时候是为了查找方便

稳定性

算法的稳定性是指, 按照他们在输入中出现的位置对相同的元素进行排序. 也就是说, 对于每个输入的需要排序的元素, 我们按照某个key进行排序, 如果这两个key相同, 那么他们的顺序应该是他们输入的时候原来的对应前后位置.

例如一个数组

1
[(3, a), [3, b], (1, m)]

我们对上面的数组, 按每个元素的m[0]为key进行排序, 如果我们采用的算法是稳定的, 那么结果应该是:

1
[(1,m), (3, a), (3, b)]

O符号

对于一个排序算法的性能比较, 经常出现的一个符号是O, 这个应该叫做渐进符号, 我们采用O来标示算法的性能, 是指我们只关注算法消耗资源增长的数量级:

  • 如果f(x)是几个项的总和, 如果有一个具有最大增长率的项, 那么我们保留这个, 忽略其他的项
  • 如果f(x)是几个因子的乘积, 则可以忽略所有的常数

算法实现

下面涉及的算法如果没有特殊说明, 那么应该是完成数组从小到大的排列

选择排序

选择排序可以理解为, 数组最左边的value一定是数组中最小的值. 那么实现就应该是从数组中取出最小的那个value, 然后放到数组的最左边, 依次递归下去

1
2
3
4
5
6
7
8
9
10
11
12
func SelectionSortDoc(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        // j应该是i左边的那个数
        for j := i+1; j < length; j++ {
            if arr[i] > arr[j] {
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }
    return arr
}

上面是最简单的实现, 但是我们看下这一步:

1
2
3
if arr[i] > arr[j] {
    arr[i], arr[j] = arr[j], arr[i]
    }

每碰到一个arr[i]大于arr[j]的数, 两个就要交换一下, 这样做了很多重复性的工作, 对吧, 因为我们只需要将arr[i]和arr[i:]中最小的那个作交换就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func SelectionSortDocM(arr []int) []int {
    length := len(arr)
    for i := 0;  i < length; i++ {
        min := i // 这里引入一个中间变量min, 用来存储最小的那个索引
        for j := i+1; j < length; j++ {
            if arr[min] > arr[j] {
                min = j
            }
        }
        // 判断min是否是i, 不是的话两个值就缓过来
        if min != i {
            arr[i], arr[min] = arr[min], arr[i]
        }
    }
    return arr
}

插入排序

插入排序就是将一个值插入到一个已经排好序的数组中.

插入排序可以理解为在一个排好序的数组arr[1,2,3...k, k+1, ...n]中, 每一个子数组arr[0:k]都是一个排好序的数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func InsertionSort(arr []int) []int {
    length := len(arr)
    for i := 1; i < length; i++ {
        j := i - 1
        key := arr[i]
        for j >= 0 && arr[j] > key {
            // 这里, 将j的位置统一右移一位
            arr[j+1] = arr[j]
            j -= 1
        }
        arr[j+1] = key
    }
    return arr
}

快速排序

快速排序的思想是, 一个排好序的数组arr[1,2,3..., k, k+1... n]中, 一定有:

  • 子数组arr[0:k]中的每一个值都不大于arr[k]
  • 子数组arr[k+1:n]中的每一个值都不小于arr[k]
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
func QuickSortDoc(arr []int) []int {
    // 声明两个匿名函数
    // 用来对数组进行迭代排序
    var recurse func(left, right int)
    // 找到数组中迭代每一次子数组中根据key排序的key的位置,
    // 这时候key应该是排好序的数组中的正确位置
    var partition func(left, right int) int

    partition = func(left, right int) int {
        key := arr[right]
        j := left
        for i := left; i < right; i++ {
            if arr[i] < key {
                arr[j], arr[i] = arr[i], arr[j]
                j++
            }
        }
        arr[j], arr[right] = arr[right], arr[j]
        return j
    }

    recurse = func(left, right int) {
        if left < right {
            pivot := (right+left) / 2
            pivot = partition(left, right)
            recurse(left, pivot-1)
            recurse(pivot+1, right)
        }
    }
    recurse(0, len(arr)-1)
    return arr
}

归并排序

// TODO 这个没有看懂, python版本的转换不到go上

归并排序的思想是合并两个已经排好序的列表形成新的列表:

  • 将未排序的列表分成n个子列表，每个子列表包含1个元素（1个元素的列表被认为是排序的）.
  • 反复合并子列表以产生新的已排序子列表，直到只剩下1个子列表。这将是排序的列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge(a, b):
    k = j = 0
    c = []
    while k < len(a) and j < len(b):
        key_a = a[k]
        key_b = b[j]
        if key_a < key_b:
            c.append(key_a)
            k += 1
        else:
            c.append(key_b)
            j += 1
    c.extend(a[k:])
    c.extend(b[j:])
    return c

def mergeSort(lst):
    if len(lst) < 2:
        return lst
    mid = len(lst) // 2
    left = mergeSort(lst[:mid])
    right = mergeSort(lst[mid:])
    return merge(left, right)

go版本:

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
func sort(arr []int) {
    var s = make([]int, len(arr)/2+1)
    if len(arr) < 2 {
        return
    }

    mid := len(arr) / 2

    sort(arr[:mid])
    sort(arr[mid:])

    if arr[mid-1] <= arr[mid] {
        return
    }

    copy(s, arr[:mid])

    l, r := 0, mid

    for i := 0; ; i++ {
        if s[l] <= arr[r] {
            arr[i] = s[l]
            l++

            if l == mid {
                break
            }
        } else {
            arr[i] = arr[r]
            r++
            if r == len(arr) {
                copy(arr[i+1:], s[l:mid])
                break
            }
        }
    }
    return
}

堆排序

没写完还…

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package heap

import (
    "sync"
)
type Int int

func (x Int) Less(than Item) bool {
    return x < than.(Int)
}


type Item interface {
    Less(than Item) bool
}

type Heap struct {
    sync.Mutex
    data []Item
    min  bool
}

func New() *Heap {
    return &Heap{
        data: make([]Item, 0),
    }
}

func NewMin() *Heap {
    return &Heap{
        data: make([]Item, 0),
        min:  true,
    }
}

func NewMax() *Heap {
    return &Heap{
        data: make([]Item, 0),
        min:  false,
    }
}

func (h *Heap) isEmpty() bool {
    return len(h.data) == 0
}

func (h *Heap) Len() int {
    return len(h.data)
}

func (h *Heap) Get(n int) Item {
    return h.data[n]
}

func (h *Heap) Insert(n Item) {
    h.Lock()
    defer h.Unlock()

    h.data = append(h.data, n)
    h.siftUp()

    return
}

func (h *Heap) Extract() (el Item) {
    h.Lock()
    defer h.Unlock()
    if h.Len() == 0 {
        return
    }

    el = h.data[0]
    last := h.data[h.Len()-1]
    if h.Len() == 1 {
        h.data = nil
        return
    }

    h.data = append([]Item{last}, h.data[1:h.Len()-1]...)
    h.siftDown()

    return
}

func (h *Heap) siftUp() {
    for i, parent := h.Len()-1, h.Len()-1; i > 0; i = parent {
        parent = i >> 1
        if h.Less(h.Get(i), h.Get(parent)) {
            h.data[parent], h.data[i] = h.data[i], h.data[parent]
        } else {
            break
        }
    }
}

func (h *Heap) siftDown() {
    for i, child := 0, 1; i < h.Len() && i<<1+1 < h.Len(); i = child {
        child = i<<1 + 1

        if child+1 <= h.Len()-1 && h.Less(h.Get(child+1), h.Get(child)) {
            child++
        }

        if h.Less(h.Get(i), h.Get(child)) {
            break
        }

        h.data[i], h.data[child] = h.data[child], h.data[i]
    }
}

func (h *Heap) Less(a, b Item) bool {
    if h.min {
        return a.Less(b)
    } else {
        return b.Less(a)
    }
}

python版本的:

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
#-*-coding:utf8-*-

def opt_heapsort(s):
    # 获取列表的长度
    sl = len(s)

    # 交换根据value的大小交换两个value
    def swap(pi, ci):
        if s[pi] < s[ci]:
            s[pi], s[ci] = s[ci], s[pi]

    #
    def sift(pi, unsorted):
        # 取最大的那个value的索引
        i_gt = lambda a, b: a if s[a] > s[b] else b
        while pi*2+2 < unsorted:
            gtci = i_gt(pi*2+1, pi*2+2)
            swap(pi, gtci)
            pi = gtci
    # heapify
    for i in range((sl//2)-1, -1, -1):
        sift(i, sl)
    # sort
    for i in range(sl-1, 0, -1):
        swap(i, 0)
        sift(0, i)

树排序

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

func main(){
    a := []int{9,5,3,5,2,1}
    TreeSort(a)
    fmt.Println(a)
}

// tree sort 的过程如下
// 定义一个treetype的变量，然后将切片的每一项元素加入到tree中
// 然后递归的将tree的元素按照左边中间右边的顺序取出来
// 1. 插入输，插入的时候，应该保证左边小于右边
type tree struct {
    value int
    left, rigth *tree
}

func TreeSort(values []int) {
    var root *tree
    for _, value := range values {
        root = add(root, value)
    }
    appendValues(values[:0], root) // 这里请求的第一个参数是和values公用一个底层数组的切片，长度为0， 容量为values原来的长度
}

func appendValues(values []int, root *tree) []int {
    if root != nil {
        values = appendValues(values, root.left)
        values = append(values, root.value)
        values = appendValues(values, root.rigth)
    }
    return values
}

func add(t *tree, value int) *tree {
    if t == nil {
        // 初始化， 刚开始的时候root为nil
        t = new(tree) // 创建一个treetype的指针，指针名字为t
        t.value = value
        return t
    }
    if value < t.value {
        t.left = add(t.left, value) // 这里递归的将value加入左子树
    } else {
        t.rigth = add(t.rigth, value)
    }
    return t
}