排序算法

常考排序

快速排序

1
func QuickSort(nums []int) []int {
2
// 思路:把一个数组分为左右两段,左段小于右段
3
quickSort(nums, 0, len(nums)-1)
4
return nums
5
6
}
7
// 原地交换,所以传入交换索引
8
func quickSort(nums []int, start, end int) {
9
if start < end {
10
// 分治法:divide
11
pivot := partition(nums, start, end)
12
quickSort(nums, 0, pivot-1)
13
quickSort(nums, pivot+1, end)
14
}
15
}
16
// 分区
17
func partition(nums []int, start, end int) int {
18
// 选取最后一个元素作为基准pivot
19
p := nums[end]
20
i := start
21
// 最后一个值就是基准所以不用比较
22
for j := start; j < end; j++ {
23
if nums[j] < p {
24
swap(nums, i, j)
25
i++
26
}
27
}
28
// 把基准值换到中间
29
swap(nums, i, end)
30
return i
31
}
32
// 交换两个元素
33
func swap(nums []int, i, j int) {
34
t := nums[i]
35
nums[i] = nums[j]
36
nums[j] = t
37
}
Copied!

归并排序

1
func MergeSort(nums []int) []int {
2
return mergeSort(nums)
3
}
4
func mergeSort(nums []int) []int {
5
if len(nums) <= 1 {
6
return nums
7
}
8
// 分治法:divide 分为两段
9
mid := len(nums) / 2
10
left := mergeSort(nums[:mid])
11
right := mergeSort(nums[mid:])
12
// 合并两段数据
13
result := merge(left, right)
14
return result
15
}
16
func merge(left, right []int) (result []int) {
17
// 两边数组合并游标
18
l := 0
19
r := 0
20
// 注意不能越界
21
for l < len(left) && r < len(right) {
22
// 谁小合并谁
23
if left[l] > right[r] {
24
result = append(result, right[r])
25
r++
26
} else {
27
result = append(result, left[l])
28
l++
29
}
30
}
31
// 剩余部分合并
32
result = append(result, left[l:]...)
33
result = append(result, right[r:]...)
34
return
35
}
Copied!

堆排序

用数组表示的完美二叉树 complete binary tree
完美二叉树 VS 其他二叉树
image.png
image.png
核心代码
1
package main
2
3
func HeapSort(a []int) []int {
4
// 1、无序数组a
5
// 2、将无序数组a构建为一个大根堆
6
for i := len(a)/2 - 1; i >= 0; i-- {
7
sink(a, i, len(a))
8
}
9
// 3、交换a[0]和a[len(a)-1]
10
// 4、然后把前面这段数组继续下沉保持堆结构,如此循环即可
11
for i := len(a) - 1; i >= 1; i-- {
12
// 从后往前填充值
13
swap(a, 0, i)
14
// 前面的长度也减一
15
sink(a, 0, i)
16
}
17
return a
18
}
19
func sink(a []int, i int, length int) {
20
for {
21
// 左节点索引(从0开始,所以左节点为i*2+1)
22
l := i*2 + 1
23
// 右节点索引
24
r := i*2 + 2
25
// idx保存根、左、右三者之间较大值的索引
26
idx := i
27
// 存在左节点,左节点值较大,则取左节点
28
if l < length && a[l] > a[idx] {
29
idx = l
30
}
31
// 存在右节点,且值较大,取右节点
32
if r < length && a[r] > a[idx] {
33
idx = r
34
}
35
// 如果根节点较大,则不用下沉
36
if idx == i {
37
break
38
}
39
// 如果根节点较小,则交换值,并继续下沉
40
swap(a, i, idx)
41
// 继续下沉idx节点
42
i = idx
43
}
44
}
45
func swap(a []int, i, j int) {
46
a[i], a[j] = a[j], a[i]
47
}
Copied!

参考

二叉堆

练习

  • 手写快排、归并、堆排序
最近更新 9mo ago