排序总结

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func bubbleSort(arr []int) {
var size = len(arr)
// 外层循环循环size-1次
for i := 0; i < size-1; i++ {
var swapped bool
// 内层循环从切片头部开始循环比较相邻元素大小
// 如果arr[j] > arr[j+1]交换之 确保每次循环后最大的元素会排到最后
for j := 0; j < size-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}

if !swapped {
// 本次循环没有交换 此时切片已经有序
return
}
}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func selectionSort(arr []int) {
var size = len(arr)
var minIndex int
// 外层循环循环size-1次
for i := 0; i < size-1; i++ {
minIndex = i
// 内层循环每次找出最小的元素
for j := i + 1; j < size; j++ {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
if minIndex != i {
// 将本次找到的最小元素放入对应位置
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func insertionSort(arr []int) {
var size = len(arr)
// 外层循环size-1次 从切片的第二个元素开始逐一为每个元素找到合适的插入位置
for i := 1; i < size; i++ {
current := arr[i]
for preIndex := i - 1; preIndex >= 0; preIndex-- {
if arr[preIndex] > current {
// 继续往前找 并挪动位置
arr[preIndex+1] = arr[preIndex]
} else {
// 找到合适的插入位置
arr[preIndex+1] = current
break
}
}
}
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func shellSort(arr []int) {
var size = len(arr)
// 初始化间隙位size/2 逐步减少间隙 直至间隙为1
for gap := size / 2; gap >= 1; gap = gap / 2 {
//将切片变为间隔h个元素有序
for i := gap; i < size; i++ {
var current = arr[i]
for preIndex := i; preIndex-gap >= 0; preIndex = preIndex - gap {
if current < arr[preIndex-gap] {
arr[preIndex] = arr[preIndex-gap]
} else {
arr[preIndex] = current
break
}
}
}
}
}

快速排序

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
func quickSort(arr []int) {
_quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) {
if left < right {
// 将切片分为两个部分
// 使得[left->pivot-1]的元素都小于等于arr[pivot], [pivot+1->right]的元素都大于arr[pivot]
pivot := partition(arr, left, right)
// 对左右两个部分重复上述过程
_quickSort(arr, left, pivot-1)
_quickSort(arr, pivot+1, right)
}
}

func partition(arr []int, left, right int) int {
// 选取array[left]作为分割基准点
i, j, pivot := left, right, arr[left]
for {
// 从右往左扫描 直到某个元素小于等于pivot
for i < j && arr[j] > pivot {
j--
}

// 从左往右扫描 直到某个元素大于pivot
for i < j && arr[i] <= pivot {
i++
}

if i < j {
// 此时可以肯定 arr[j] <= pivot 同时 arr[i] > pivot, 交换a[i], a[j]
arr[i], arr[j] = arr[j], arr[i]
} else {
// 扫描完毕
break
}
}

arr[i], arr[left] = arr[left], arr[i]
return 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
func mergeSort(arr []int) []int {
var size = len(arr)
if size <= 1 {
// 只有一个值 无需排序
return arr
}

// 分成左右两组 分别继续归并排序
var mid = size / 2
var left = mergeSort(arr[:mid])
var right = mergeSort(arr[mid:])
// 合并左右两组排序结果
return merge(left, right)
}

func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] <= right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
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
func heapSort(arr []int) {
var size = len(arr)
// 构建大顶堆
for i := size/2 - 1; i >= 0; i-- {
// 从第一个非叶子节点从下至上, 从左到右调整结构
adjustHeap(arr, i, size)
}

// 下沉堆定元素+重新调整堆结构
for i := size - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
adjustHeap(arr, 0, i)
}
}

func adjustHeap(arr []int, i, size int) {
var tmp = arr[i]
for k := i*2 + 1; k < size; k = k*2 + 1 {
//从i结点的左子结点开始,也就是2i+1处开始
if k+1 < size && arr[k] < arr[k+1] {
//如果左子结点小于右子结点,k指向右子结点
k++
}

if arr[k] > tmp {
//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k]
i = k
} else {
break
}
}
//将temp值放到最终的位置
arr[i] = tmp
}

非比较类型排序

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
119
120
121
122
123
124
125
126
// 计数排序
func countingSort(arr []int) {
var maxValue = maxValue(arr)
// 分配一个能容纳0-maxValue整数的切片
var bucket = make([]int, maxValue+1)
// 将每个元素直接存到对应位置
for _, value := range arr {
bucket[value] += 1
}

sortedIndex := 0
// 存放元素位置的顺序就是元素排序后的顺序
for i := range bucket {
for {
if bucket[i] > 0 {
arr[sortedIndex] = i
bucket[i]--
sortedIndex++
} else {
break
}
}
}
}

// 桶排序 计数排序的升级版 利用函数映射
func bucketSort(arr []int) {
//桶数
var size = len(arr)
var maxValue = maxValue(arr)
//二维切片
buckets := make([][]int, size)
//分配入桶
index := 0
for i := 0; i < size; i++ {
index = arr[i] * (size - 1) / maxValue //函数映射
buckets[index] = append(buckets[index], arr[i])
}

// 按顺序遍历桶取出数据
tmpPos := 0
for i := 0; i < size; i++ {
bucketLen := len(buckets[i])
if bucketLen > 0 {
// 桶内排序
// 此处实现插入排序方式,其实可以用任意其他排序方式
insertionSort(buckets[i])
copy(arr[tmpPos:], buckets[i])
tmpPos += bucketLen
}
}
}

// 获取数组最大元素
func maxValue(arr []int) (max int) {
if len(arr) == 0 {
return 0
}

max = arr[0]
for _, value := range arr {
if value > max {
max = value
}
}

return
}

// 基数排序
// 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零
// 然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
// 基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital)
// LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
// 下面是实现的LSD版本
func radixSort(arr []int) {
var (
size = len(arr)
tmp = make([]int, size, size)
radix = 1
maxDigit = maxDigit(arr)
)

var i, j, k int
for i = 0; i < maxDigit; i++ { //进行maxDigit次排序
// count index 0->9对应每个位上的数字
// count value 对应每个位上数字出现次数
var count = make([]int, 10)
for j = 0; j < size; j++ {
k = (arr[j] / radix) % 10
count[k]++
}

for j = 1; j < 10; j++ {
count[j] = count[j-1] + count[j]
}
// 逆序
for j = size - 1; j >= 0; j-- {
k = (arr[j] / radix) % 10
tmp[count[k]-1] = arr[j]
count[k]--
}

for j = 0; j < size; j++ {
arr[j] = tmp[j]
}

// 十进制位数增加
radix = radix * 10
}
}

//求数组元素的十进制位数
func maxDigit(arr []int) (ret int) {
if len(arr) == 0 {
return 0
}
var radix = 1
for _, value := range arr {
for value >= radix {
radix = radix * 10
ret++
}
}
return
}