排序算法：归并排序，golang实现

目录

前言

归并排序

代码示例

1. 算法包

2. 归并排序代码

3. 模拟程序

4. 运行程序

5. 从大到小排序

归并排序主要操作

1. 合并

2. 分割（Divide）与递归排序（Conquer）

总体思想

循环次数测试

假如 10 条数据进行排序

假如 20 条数据进行排序

假如 30 条数据进行排序

假设 5000 条数据，对比 冒泡、选择、插入、快速、堆

归并排序的适用场景

1. 大数据集

2. 链表排序

3. 外部排序

4. 稳定性需求

---

前言

在实际场景中，选择合适的排序算法对于提高程序的效率和性能至关重要，本节课主要讲解"归并排序"的适用场景及代码实现。

归并排序

归并排序（Merge Sort）是一种分而治之的排序算法。它将一个大列表分成两个小列表，分别对这两个小列表进行排序，然后将排序好的小列表合并成一个最终的排序列表。归并排序的关键在于合并（Merge）过程，它确保了在合并的过程中，两个已排序的序列被合并成一个新的、有序的序列。

代码示例

下面我们使用Go语言实现一个归并排序

1. 算法包

创建一个 pkg/algorithm.go

touch pkg/algorithm.go

（如果看过上节课的堆排序，则已存在该文件，我们就不需要再创建了）

2. 归并排序代码

打开 pkg/algorithm.go 文件，代码如下

从小到大 排序

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// HeapSort 堆排序
...// heapify 将以 i 为根的子树调整为最大堆
...// MergeSort 归并排序
func MergeSort(arr []int) []int {if len(arr) <= 1 {return arr}// 找到中点，分割数组mid := len(arr) / 2left := MergeSort(arr[:mid])right := MergeSort(arr[mid:])// 合并两个已排序的切片return merge(left, right)
}// merge 函数用于合并两个已排序的切片
func merge(left, right []int) []int {var result []inti, j := 0, 0for i < len(left) && j < len(right) {if left[i] < right[j] {result = append(result, left[i])i++} else {result = append(result, right[j])j++}}// 如果左侧有剩余，则追加到结果切片result = append(result, left[i:]...)// 如果右侧有剩余，则追加到结果切片result = append(result, right[j:]...)return result
}

3. 模拟程序

打开 main.go 文件，代码如下：

package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片，这里我们模拟 10 个元素arr := []int{98081, 27887, 31847, 84059, 2081, 41318, 54425, 22540, 40456, 3300}fmt.Println("arr 的长度：", len(arr))fmt.Println("Original data:", arr) // 先打印原始数据newArr := pkg.MergeSort(arr)       // 调用归并排序fmt.Println("New data:  ", newArr) // 后打印排序后的数据
}

4. 运行程序

go run main.go

能发现， Original data 后打印的数据，正是我们代码中定义的切片数据，顺序也是一致的。

New Data 后打印的数据，则是经过归并排序后的数据，是从小到大的。

5. 从大到小排序

如果需要 从大到小 排序也是可以的，在代码里，需要将两个 if 判断比较的 符号 进行修改。

修改 pkg/algorithm.go 文件：

package pkg// BubbleSort 冒泡排序
...// SelectionSort 选择排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
...// partition 分区操作
...// HeapSort 堆排序
...// heapify 将以 i 为根的子树调整为最大堆
...// MergeSort 归并排序
func MergeSort(arr []int) []int {if len(arr) <= 1 {return arr}// 找到中点，分割数组mid := len(arr) / 2left := MergeSort(arr[:mid])right := MergeSort(arr[mid:])// 合并两个已排序的切片return merge(left, right)
}// merge 函数用于合并两个已排序的切片
func merge(left, right []int) []int {var result []inti, j := 0, 0for i < len(left) && j < len(right) {if left[i] > right[j] {result = append(result, left[i])i++} else {result = append(result, right[j])j++}}// 如果左侧有剩余，则追加到结果切片result = append(result, left[i:]...)// 如果右侧有剩余，则追加到结果切片result = append(result, right[j:]...)return result
}

只需要一丁点的代码即可

从 package pkg 算第一行，上面示例中在第四十五行代码，我们将 "<" 改成了 ">" ，这样就变成了 从大到小排序了

归并排序主要操作

主要操作包括 分割 和 合并

1. 合并

合并操作由 merge 函数实现，它接收两个已排序的切片 left 和 right，并返回一个新的、包含两个切片所有元素且已排序的切片。

• 初始化：首先，创建一个空的切片 result 用于存储合并后的结果。同时，使用两个索引 i 和 j 分别指向 left 和 right 的起始位置
• 比较与合并：然后，使用一个循环，比较 left[i] 和 right[j] 的大小。将较小的元素追加到 result 中，并移动相应的索引。这个过程一直持续到任一切片中的所有元素都被添加到 result 中
• 追加剩余元素：如果 left 和 right 中还有剩余的元素（即某个切片的索引没有遍历完），则直接将剩余的元素追加到 result 的末尾。这是因为在循环结束时，剩余的元素一定是已排序的（它们来自原始的已排序切片）

2. 分割（Divide）与递归排序（Conquer）

分割与递归排序操作由 mergeSort 函数实现。

• 基本情况：如果输入的切片 arr 的长度小于或等于 1，则不需要排序，直接返回该切片。因为单个元素或空切片都可以被认为是已排序的
• 分割：找到切片的中点 mid，将切片分为两部分：arr[:mid] 和 arr[mid:]
• 递归排序：对着两部分分别调用 mergeSort 函数进行递归排序。这会将问题分解成更小的子问题，直到子问题小到满足基本情况
• 合并：最后，使用 merge 函数将这两个递归排序后的切片合并成一个有序的切片，并返回该切片

总体思想

归并排序通过递归地将数组分解成越来越小的半子表，对半子表排序，然后再将排好序的半子表合并成有序的表来工作。这个过程需要额外的存储空间来存放合并后的数组，因此其空间复杂度为 O(n)。然而，归并排序的时间复杂度是稳定的 O(n log n)，并且由于其分治特性，它在实际应用中非常有效，尤其是在处理大数据集时。

循环次数测试

参照上面示例进行测试（因考虑到每次手动输入 10 条、20 条、30 条数据太繁琐，所以我写了一个函数，帮助我自动生成 0到100000 的随机整数）

假如 10 条数据进行排序

总计循环了 32 次

假如 20 条数据进行排序

总计循环了 84 次

假如 30 条数据进行排序

总计循环了 137 次

假设 5000 条数据，对比 冒泡、选择、插入、快速、堆

• 冒泡排序：循环次数 12,502,499 次
• 选择排序：循环次数 12,502,499 次
• 插入排序：循环次数 6,323,958 次
• 快速排序：循环次数 74,236 次
• 堆排序：循环次数 59,589 次
• 归并排序：循环次数 60,288 次

归并排序的适用场景

归并排序在以下场景表现良好

1. 大数据集

对于非常大的数据集，归并排序通常比快速排序或插入排序更有效，因为归并排序的时间复杂度是 O(n log n)，并且它的性能相对稳定，不会因数据集的不同而大幅度变化

2. 链表排序

由于归并排序在合并过程中不需要额外的空间（除了递归栈），所以在链表排序时非常高效。链表数据结构的特性使得分割和合并操作相对简单

3. 外部排序

当数据集太大，无法全部加载到内存时，可以使用归并排序的外部版本。在这个版本中，数据被分割成多个块，每块单独排序后存储在磁盘上，然后通过归并操作将它们合并成一个有序的文件

4. 稳定性需求

归并排序是稳定的排序算法，这意味着相等的元素在排序后仍然保持原来的顺序。这在需要保持元素原始顺序的某些应用中非常有用

尽管归并排序在很多场景下都很有用，但它也有缺点，主要是需要额外的空间 O(n) 来存储临时数组。这在内存受限的情况下可能是一个问题。