苦与乐
0%

sort

Posted on
Symbols count in article: Reading time ≈ NaN:aN

排序算法

主要关注常见的十种排序算法：

  • 快速排序
  • 冒泡排序
  • 归并排序
  • 插入排序
  • 希尔排序
  • 选择排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

测试用例

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
import (
	"testing"
)

func TestSort(t *testing.T) {
	tcs := []struct {
		name   string
		items  []int
		expect []int
	}{
		{
			"case1",
			[]int{5, 2, 3, 1, 4},
			[]int{1, 2, 3, 4, 5},
		},
		{
			"case2",
			[]int{1, 1, 3, 1, 4},
			[]int{1, 1, 1, 3, 4},
		},
		{
			"case3",
			[]int{1, 1, 1, 1, 1},
			[]int{1, 1, 1, 1, 1},
		},
		{
			"case4",
			[]int{5, 4, 3, 2, 1},
			[]int{1, 2, 3, 4, 5},
		},
		{
			"case5",
			[]int{1},
			[]int{1},
		},
		{
			"case6",
			[]int{1, 2, 3},
			[]int{1, 2, 3},
		},
	}

	check := func(items []int, expect []int) bool {
		if len(items) != len(expect) {
			return false
		}
		for i := 0; i < len(items); i++ {
			if items[i] != expect[i] {
				return false
			}
		}
		return true
	}

	for _, tc := range tcs {
		t.Logf("Run case: %s\n", tc.name)
		QSort(tc.items)
		if !check(tc.items, tc.expect) {
			t.Errorf("%s Failed, expect: %v, got: %v\n", tc.name, tc.expect, tc.items)
		}
	}
}

快速排序

思路

首先，设定一个基准值（第一个、最后一个或者随机一个值）；

然后，根据基准值，把数据集合划分为两个部分，一个部分元素都大于基准值，一个部分元素都小于等于基准值；

然后，对划分的两个部分，递归进行1，2两步；

最后，直到数据集合元素小于等于1为止。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func QSort(items []int) {
	if len(items) <= 1 {
		return
	}
	i, j := 1, len(items)-1
	temp := items[0]

	for i <= j {
		if items[i] > temp {
			items[i], items[j] = items[j], items[i]
			j--
		} else {
			i++
		}
	}

	// i - 1 is count of item which little and equal to temp
	// so, we just move temp to right index
	items[i-1], items[0] = items[0], items[i-1]

	QSort(items[0 : i-1])
	QSort(items[i:])
}

冒泡排序

思路

依次遍历数据集合的相邻的每对数据，如果第一个大于第二个，则交换它们的位置；

每次遍历数据集合，会确定一个最大值，因此，每次遍历会减少下一次遍历的集合数量；

遍历n次，即完成排序。

实现

1
2
3
4
5
6
7
8
9
func BubbleSort(items []int) {
	for i := 0; i < len(items); i++ {
		for j := 1; j < len(items)-i; j++ {
			if items[j] < items[j-1] {
				items[j-1], items[j] = items[j], items[j-1]
			}
		}
	}
}

归并排序

思路

  • 把数据集合拆分为数量相当两个子集合（n/2和n-n/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
func MergeSort(items []int) {
	if len(items) <= 1 {
		return
	}
	m := len(items) / 2
	MergeSort(items[0:m])
	MergeSort(items[m:])

	mergeHelper(items, 0, m, len(items))
}

func mergeHelper(items []int, l, m, r int) {
	sorted := make([]int, (r - l))
	i, j := l, m
	k := 0

	for i < m && j < r {
		if items[i] > items[j] {
			sorted[k] = items[j]
			j++
		} else {
			sorted[k] = items[i]
			i++
		}
		k++
	}
	for i < m {
		sorted[k] = items[i]
		k++
		i++
	}
	for j < r {
		sorted[k] = items[j]
		k++
		j++
	}

	// update items
	for _, st := range sorted {
		items[l] = st
		l++
	}
}