笔记整理全部整理于文档库页面 点我前往

排序

此文档处于需补充阶段 我会在适当的时候(等我学到的时候)继续补充。

参考资料

动图来源 - 菜鸟教程

内部排序

根据需要将需要处理的数据都加载到内部存储器中进行排序

冒泡排序 (Bubble Sorting)

冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数。经过第一次遍历之后,最大的数就在最右侧了;第二次遍历之后,第二大的数就在右数第二个位置了;以此类推。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func bubbleSort(array []int)[]int{
flag := true
for i := 0; i < lenth; i++ {
for j := 0; j < lenth - 1; j++ {
if array[j] > array[j + 1]{
array[j], array[j + 1] = array[j + 1], array[j]
flag = false //优化部分 如果flag 没有变成false 则表示没有发生交换
}
}
if flag {
break //直接跳出排序
}
}
return array
}

选择式排序法 (SelectionSort)

选择排序提高了冒泡排序的性能,它每遍历一次列表只交换一次数据,在未排序序列中寻找最大/最小的元素,存放到排序序列的起始位置,并从余下未排序序列中继续寻找最大/最小的元素,并放置到已排序序列的末端,直至结束。

img

1
2
3
4
5
6
7
8
9
10
11
func selectionSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := i + 1; j < length; j++ {
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i] //从未排序序列中继续寻找最小值,并放置到已排序序列的末端
}
}
}
return arr
}

插入式排序 (InsertionSort)

和扑克牌一样,将首个元素视为有序序列,将其余的视为未排序元素,从头至尾扫描未排序序列,将扫描到的元素插入到有序序列的适当位置,如果相等则插入到该已排序元素的后面。

img

1
2
3
4
5
6
7
8
9
func insertionSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := i; j > 0 && arr[j] < arr[j-1]; j-- { // 判断要取的未排序首位是否小于已排序的末尾
arr[j-1], arr[j] = arr[j], arr[j-1] //符合要求就 互换位置
}
}
return arr
}

外部排序法

数据量过大,无法全部加载到内存中,需要借用外部存储进行排序

合并排序法

直接合并排序法