发表algorithm20 分钟读完 (大约2968个字)0 次访问

八大排序算法及其代码实现

选择排序

原理

每次选择数组中的最小元素，排在第一个位置

算法步骤

1
2
3
4
5
6
7
8
[38,65,97,76,13,27,49]
13 [65 97 76 38 27 49]
13 27 [97 76 38 65 49]
13 27 38 [76 97 65 49]
13 27 38 49 [97 65 76]
13 27 38 49 65 [97 76]
13 27 38 49 65 76 [97]
13 27 38 49 65 76 97

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func SelectSort(data []int) {
	length := len(data)

	for i := 0; i < length; i++ {
		// 记录第一个数据
		min := data[i]
		index := i

		// 获取到最小的值以及对应的索引
		for j := i + 1; j < length; j++ {
			if min > data[j] {
				min = data[j]
				index = j
			}
		}
		// 如果最小的值不是当前序列的第一个值
		// 那么需要进行交换
		if index != i {
			// 交换最小值
			data[index], data[i] = data[i], min
		}
	}
}

插入排序

原理

假设之前的数组都是一个有序序列，其余的记录为无序序列，从这些无序序列中不断选取数据，插入到前面已经排序好的有序序列中

算法步骤

1
2
3
4
5
6
7
[38] 65 97 76 13 27 49
[38 65] 97 76 13 27 49
[38 65 97] 76 13 27 49
[38 65 76 97] 13 27 49
[13 38 65 76 97] 27 49
[13 27 38 65 76 97] 49
[13 27 38 49 65 76 97]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func InsertSort(data []int) {
	for i := 1; i < len(data); i++ {
		tmp, j := data[i], i
		// 如果第j-1个元素比第i个元素大
		// 不满足递增的条件，第i个需要移动到前面
		if data[j-1] > tmp {
			// 将第i个元素移动到前面的适当位置
			// 也就是将元素不断的向右边移动，直到找到合适的位置摆放
			for j >= 1 && data[j-1] > tmp {
				data[j] = data[j-1]
				j--
			}
		}
		// 将当前遍历到的值填充到对应的位置
		data[j] = tmp
	}
}

冒泡排序

原理

基本思路: 从第一个元素开始一次对相邻的记录进行比较， 当前面的记录大于后面的记录，交换其位置，进行一轮比较和换位之后，n个记录中的最大记录将位于第n位

算法步骤

1
2
3
4
5
6
7
8
{38 65 97 76 13 27 49}
38 65 76 13 27 49 [97]
38 65 13 27 49 [76 97]
38 13 27 49 [65 76 97]
13 27 38 [49 65 76 97]
13 27 [38 49 65 76 97]
13 [27 38 49 65 76 97]
[13 27 38 49 65 76 97]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func BubbleSort(nums []int) {
	flag := false
	n := len(nums)
	// 这里采用的是不断将最大的移动到数组的最后面
	// 当然也可以将最小的移动到最前面来
	for i := 0; i < n ; i ++{
		for j := 0; j < n-1 -i; j ++{
			if nums[j] > nums[j+1]{
				nums[j], nums[j+1] = nums[j+1], nums[j]
				flag = true
			}
		}
		if !flag{
			fmt.Println("一轮遍历中没有进行交换，说明数组已经有序")
			break
		}
		fmt.Println(nums)
	}
}

归并排序

原理

将一个数组拆成两份，每一份进行递归操作之后都是有序的，然后进行合并，最终是有序的。

算法步骤

1
2
3
4
5
6
7
{38 65 97 76 13 27 49}
[38 65 97 76] [13 27 49] 
[38 65] [97 76] [13 27] [49]
[38] [65] [97] [76] [13] [27] [49]  // 全部分裂
[38 65] [76 97] [13 27] [49] // 开始进行合并
[38 65 76 97] [13 27 49]
[13 27 38 49 65 76 97]

代码实现

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 MergerSort(nums []int) {
	mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	mid := (right-left)/2 + left
	mergeSort(nums, left, mid)
	mergeSort(nums, mid+1, right)
	merge(nums, left, mid, right)
}

// 合并两个数组，分别是从 left -> mid , mid -> right 索引开始
func merge(nums []int, left, mid, right int) {
	// 辅助数据
	tmp := make([]int, right-left+1)

	for i := left; i <= right; i++ {
		tmp[i-left] = nums[i]
	}
	i, j := 0, mid-left+1
	k := left
	for k <= right && i <= mid-left && j <= right-left {
		if tmp[i] > tmp[j] {
			nums[k] = tmp[j]
			k++
			j++
		} else {
			nums[k] = tmp[i]
			i++
			k++
		}
	}
	for i <= mid-left {
		nums[k] = tmp[i]
		i++
		k++
	}

	for j <= right-left {
		nums[k] = tmp[j]
		j++
		k++
	}
}

快速排序

快速排序是一种非常高效的排序算法，它采用分而治之的思想，把大的拆分成小的，小的再拆分成更小的。

原理

对于一组给定的记录，通过一趟排序之后，将原来的序列分成两部分，其中一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归改过程，直到序列中的所有记录均有序为止

可以直接认为是找到了一个分界点，比如如果需要实现递增，那么左边都是小于该数，右边都是大于该数

算法步骤

  1. 分解：将输入的序列array[m...n] 划分成两个非空子序列array[m...k]和array[k+1...n]，使得array[k+1...n]中的任意一个元素都不小于array[m...k]中的元素
  2. 递归求解：通过递归调用快速排序算法分别对array[m...k]和array[k+1...n]进行排序
  3. 合并：由于对分解出来的两个子序列的排序是就地进行的，所以在array[m...k]和array[k+1...n]都排好序后不需要执行任何计算array[m...n]

代码实现

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
func sort(arr []int, left, right int) {
	if left >= right {
		return
	}

	i := left
	j := right

	// 选定一个分界点
    // 如果直接下面这种方式取的话，如果数据是有序的，那么时间复杂度相比较会比较高
	index := arr[i]
    // 也可以随机挑选一个
    
   	// rand.Seed(time.Now().UnixNano())
	// var random int 
	// random = rand.Int() % (right-left+1) + left
    // 将随机选中的移动到最左边
	// arr[i], arr[random] = arr[random], arr[i]
    // 这里只是为了更新上面的index，如果直接写的话，可以去掉上的赋值，直接使用index:= arr[i]
	// index = arr[i]

	for i < j {
		// 右边界不断向左移动，如果碰到比index小的数据
		// 则需要将左边的i对应的数据赋值为对应的值
		for i < j && arr[j] >= index {
			j--
		}
		if i < j {
			arr[i] = arr[j]
			i++
		}
		// 左边界不断往右移动，如果碰到比index小的数据
		// 则将右边的这个数据赋值索引j对应的数据
		for i < j && arr[i] <= index {
			i++
		}

		if i < j {
			arr[j] = arr[i]
			j--
		}


	}
    // 索引i表示的就是
    arr[i] = index

	// 排序左边子数组
	sort(arr, left, i-1)
	// 排序右边
	sort(arr, i+1, right)
}

func QuickSort(arr []int) {
	sort(arr, 0, len(arr)-1)
}

​

基准关键字的选取

常用的基准关键字的选取有以下方式:

  1. 选取首尾，中间位置上的中值作为基准关键字
  2. 选取随机数

希尔排序

原理

类似插入排序，但是不是相邻的进行，而是会跳过几个位置

算法步骤

1
2
3
4
5
6
7
8
9
10
11
{38, 65, 97, 76, 13, 27, 49}
step为: 3   [38 65 97 76 13 27 49]  // 索引 3 和 0 进行比较并交换
step为: 3   [38 13 97 76 65 27 49]  // 索引 4 和 1 进行比较并交换
step为: 3   [38 13 27 76 65 97 49]  // 索引 5 和 2 进行比较并交换
step为: 3   [38 13 27 49 65 97 76]  // 索引 6 和 3 进行比较并交换
step为: 1   [13 38 27 49 65 97 76]  // 索引 1 和 0 进行比较并交换
step为: 1   [13 27 38 49 65 97 76]  // 索引 2 和 1 进行比较并交换
step为: 1   [13 27 38 49 65 97 76]  // 索引 3 和 2 进行比较并交换
step为: 1   [13 27 38 49 65 97 76]  // 索引 4 和 3 进行比较并交换
step为: 1   [13 27 38 49 65 97 76]  // 索引 5 和 4 进行比较并交换
step为: 1   [13 27 38 49 65 76 97]  // 索引 6 和 5 进行比较并交换

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func ShellSort(nums []int) {
	// 步长
	for step := len(nums) / 2; step > 0; step /= 2 {
		for i := step ; i < len(nums); i++ {
			// 直接插入排序
			if nums[i] < nums[i-step] {
				j, tmp := i, nums[i]
				// 找出同一组中比tmp小的值，往后面移动step个位置
				for j >= step && tmp < nums[j-step] {
					nums[j] = nums[j-step]
					j -= step
				}
				nums[j] = tmp
			}
		}
	}
}

堆排序

原理

这里说一下递增排序，使用大根堆

大根堆有一个特点，那就是堆的顶部是整个数组中最大的元素，一个比较简单的想法就是，我把这个元素拿出来，然后插入到其他的数组中，堆中 pop 出堆顶的元素，依次进行，便可以获取到一个排序序列，不过这种思路需要多余的一个数组，其实没有必要，我们来自己看看删除元素的过程。

首先，将堆顶的元素和最后一个元素进行交换，然后 size--，进行向下冒泡 down，删除掉最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
func pop(arr *[]int) int {
	nums := *arr
	n := len(nums) - 1
    // 交换
	nums[0], nums[n] = nums[n], nums[0]
	down(nums, 0, n)
	x := nums[n]
	// 删除最后一个元素
	*arr = (*arr)[:n]
	return x
}

注意这里删除最后一个元素，我们可以把这个元素保留在这里，但是让 down 的时候不接触到这个元素不就行了？这个很好实现，因为一般我们都是使用元素的长度作为 down 的一个 size 参数，我们指定一下就好，主要的逻辑代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
func heapSort(nums []int) {
	size := len(nums)
	// 首先建堆
	buildHeap(nums)
	// 然后这个时候最大的元素在第一个
	for size > 1 {
		// 第一个元素和最后一个进行交换
		nums[0], nums[size-1] = nums[size-1], nums[0]
		size--
		down(nums, 0, size)
	}
}

代码实现

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
// 建大根堆
func buildHeap(nums []int) {
	size := len(nums)
	for i := size / 2; i >= 0; i-- {
		down(nums, i, size)
	}
}

// 插入元素的时候需要使用
func up(nums []int, i int) {
	for {
		// 父结点计算公式！！
		parent := (i - 1) / 2
		// 如果父结点大于子节点了，说明不需要调换，已经满足条件了
		// 如果 i == parent 说明 i = 0 了，没有父结点，也不需要调换
		if i == parent || nums[parent] > nums[i] {
			break
		}
		// 父结点没有子节点i的值大，需要调换
		nums[parent], nums[i] = nums[i], nums[parent]
	}
}

// 初始化的时候需要建堆
// 删除元素的时候需要down：
// 将第一个元素和最后一个元素进行调换, 然后重新 down(nums, 0, size)
func down(nums []int, i int, size int) {
	left, right := 2*i+1, 2*i+2
	j := i

	// 找到最大的元素的下标
	if left < size && nums[left] > nums[j] {
		j = left
	}
	if right < size && nums[right] > nums[j] {
		j = right
	}

	if j != i {
		nums[i], nums[j] = nums[j], nums[i]
		down(nums, j, size)
	}
}

// 不用递归也可以
func down2(nums []int, i, size int) {
	for {
		left, right := i*2+1, i*2+2
		// 说明i是叶子节点
		if left >= size {
			break
		}
		// 找到最大的节点
		largest := i
		if left < size && nums[left] > nums[largest] {
			largest = left
		}
		if right < size && nums[right] > nums[largest] {
			largest = right
		}

		if largest != i {
			nums[i], nums[largest] = nums[largest], nums[i]
			i = largest
		} else {
			// 如果最大的节点就是本身，那么后面也不需要进行操作了
			break
		}
	}
}

// 从堆中弹出一个数
// 首先将堆顶的元素和最后一个元素进行调换，然后进行down操作
func pop(arr *[]int) int {
	nums := *arr
	n := len(nums) - 1
	nums[0], nums[n] = nums[n], nums[0]
	down(nums, 0, n)
	x := nums[n]

	*arr = (*arr)[:n]
	return x
}

func HeapSort(nums []int) {
	size := len(nums)
	// 首先建堆
	buildHeap(nums)
	// 然后这个时候最大的元素在第一个
	for size > 1 {
		// 第一个元素和最后一个进行交换
		nums[0], nums[size-1] = nums[size-1], nums[0]
		size--
		down(nums, 0, size)
	}
}

计数排序

原理

设置一个长度为元素最大值最小值的空间，将元素一个一个对应一个索引，如果这个索引中已经存在元素，那么对应的值+1，说明这个索引处对应多个元素，最后遍历一遍这个索引空间，值为0的不需要添加，值为多个的一次添加到原数组中

计数排序适合于数组中的值在一定范围内的数据，比如说年龄，数据可能需要进行整理，比如 [10000, 20000] 的数据，我们可以首先整理为 [0, 10000]，然后再转换回去。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 比如我们需要排序年龄，那么我们可以估算年龄在[0,200]中
func CountingSort(nums []int) {
    count := make([]int, 200)
    for _, num := range nums {
        count[num] ++ 
    }
    index := 0 
    for i :=0; i < len(count); i ++ {
        // 出现了多少次，排序后添加到原数组多少次
        for j:= 0; j < count[i]; j++ {
            nums[index] = i 
            index ++ 
        }
    }
}

总结

下表给出了每种排序算法的稳定性和效率的比较：

排序方法 最好时间 平均时间 最坏时间 辅助储存 稳定性 备注
简单选择排序 $$O(n^2)$$ $$O(n^2)$$ $$O(n^2)$$ $$O(1)$$ 不稳定 n小时较好
直接插入排序 $$O(n)$$ $$O(n^2)$$ $$O(n^2)$$ $$O(1)$$ 稳定 大部分有序时较好
冒泡排序 $$O(n)$$ $$O(n^2)$$ $$O(n^2)$$ $$O(1)$$ 稳定 n小时较好
希尔排序 $$O(n)$$ $$O(n\log n)$$ $$O(sn)\ 1<s<2$$ $$O(1)$$ 不稳定 s是所选分组
快速排序 $$O(n\log n)$$ $$O(n\log n)$$ $$O(n^2)$$ $$O(\log n)$$ 不稳定 n大时较好
堆排序 $$O(n\log n)$$ $$O(n\log n)$$ $$O(n\log n)$$ $$O(1)$$ 不稳定 n大时较好
归并排序 $$O(n\log n)$$ $$O(n\log n)$$ $$O(n\log n)$$ $$O(n)$$ 稳定 n大时较好

如果想要更直观的看排序过程，推荐使用 Data Structure Visualizations 这个网站进行理解。

生活杂笔，学习杂记，偶尔随便写写东西。

八大排序算法及其代码实现

https://junhaideng.github.io/2021/11/29/alg/sort/

作者

Edgar

发布于

2021-11-29

更新于

2021-12-21

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我
CSDN知乎

最新文章

标签

Cargo1
FTS2
Gin1
GitHub1
GitHub Actions1
Go8
HTTP2
Language1
OTS3
Rust3
Scheduler1
api1
blog1
container1
cryptography9
deploy1
design3
design pattern1
distribution4
docker1
framework1
fundamental2
git1
hash1
hash-based8
package1
proxy1
signature8
sort1
source code3
stateless1
testing1
tools1
×