悟云

排序总结

发表于

冒泡排序

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
}