app网站建站系统策划方案,网站空间商排名,淘宝二官方网站是做啥的,甘肃网站建设方案及案例目录
前言
归并排序
代码示例
1. 算法包
2. 归并排序代码
3. 模拟程序
4. 运行程序
5. 从大到小排序
归并排序主要操作
1. 合并
2. 分割#xff08;Divide#xff09;与递归排序#xff08;Conquer#xff09;
总体思想
循环次数测试
假如 10 条数据进行排序…目录
前言
归并排序
代码示例
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/pkgfmt
)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) 来存储临时数组。这在内存受限的情况下可能是一个问题。
