归并排序：稳定排序的典范

归并排序稳定排序的典范算法原理核心思路归并排序是一种基于分治思想的稳定排序算法其核心思想是分解将数组分成两个子数组递归地对两个子数组进行排序合并将两个已排序的子数组合并成一个有序数组复杂度分析时间复杂度O(n log n)其中 n 是数组的长度。无论输入数据的分布如何时间复杂度都是 O(n log n)。空间复杂度O(n)需要额外的空间来存储合并过程中的临时数组。代码实现def merge_sort(arr): 归并排序 if len(arr) 1: return arr # 分解将数组分成两个子数组 mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) # 合并将两个已排序的子数组合并成一个有序数组 return merge(left, right) def merge(left, right): 合并两个已排序的数组 result [] i j 0 # 比较两个数组的元素将较小的元素加入结果数组 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 将剩余的元素加入结果数组 result.extend(left[i:]) result.extend(right[j:]) return result # 原地归并排序需要额外的空间 def merge_sort_in_place(arr, temp, low, high): 原地归并排序 if low high: mid (low high) // 2 merge_sort_in_place(arr, temp, low, mid) merge_sort_in_place(arr, temp, mid 1, high) merge_in_place(arr, temp, low, mid, high) def merge_in_place(arr, temp, low, mid, high): 原地合并两个已排序的子数组 # 将元素复制到临时数组 for i in range(low, high 1): temp[i] arr[i] i low # 左子数组的指针 j mid 1 # 右子数组的指针 k low # 原数组的指针 # 比较两个子数组的元素将较小的元素放回原数组 while i mid and j high: if temp[i] temp[j]: arr[k] temp[i] i 1 else: arr[k] temp[j] j 1 k 1 # 将左子数组剩余的元素放回原数组 while i mid: arr[k] temp[i] i 1 k 1 # 将右子数组剩余的元素放回原数组已经在正确的位置 # while j high: # arr[k] temp[j] # j 1 # k 1代码解析基础实现递归终止条件如果数组长度小于等于 1直接返回数组。分解将数组分成两个子数组递归地对两个子数组进行排序。合并将两个已排序的子数组合并成一个有序数组。原地实现分解将数组分成两个子数组递归地对两个子数组进行排序。合并使用临时数组来辅助合并两个已排序的子数组。实战技巧优化技巧小规模子数组对于小规模的子数组例如长度小于 10使用插入排序可以提高性能。避免复制在合并操作中尽量减少元素的复制次数提高效率。并行处理对于大规模数据可以使用并行处理来提高排序速度。稳定性归并排序是一种稳定的排序算法即相等元素的相对顺序在排序前后保持不变。这在某些场景下非常重要例如当需要按照多个关键字排序时。错误分析常见错误边界条件处理错误没有正确处理数组长度为 0 或 1 的情况。合并操作错误在合并两个子数组时没有正确处理剩余元素。临时数组使用错误在原地归并排序中没有正确使用临时数组。性能问题对于大规模数据没有进行适当的优化导致性能下降。扩展思考变种问题自底向上的归并排序不需要递归从最小的子数组开始逐步合并。外排序当数据量超过内存容量时使用归并排序的思想进行外排序。多路归并合并多个有序数组。计数归并排序结合计数排序的思想提高排序效率。应用场景归并排序在以下场景中有着广泛的应用稳定排序需要保持相等元素相对顺序的场景。外排序当数据量超过内存容量时。链表排序归并排序特别适合链表排序因为不需要额外的空间。逆序对计数可以通过归并排序来高效计算逆序对的数量。个人实践感悟最近在准备转正答辩每天被各种算法题和合并冲突吓醒救命今天复习归并排序算法突然想到刚实习时第一次写归并排序代码的场景。当时我还不知道如何正确实现合并操作结果写了一个时间复杂度为 O(n²) 的版本被mentor嘲笑了一整天麻了现在再看这个算法其实归并排序的核心就是分治思想和合并操作。通过将数组分解成小的子数组分别排序后再合并可以得到高效的排序算法。这让我意识到算法的学习真的是一个循序渐进的过程从一无所知到熟练掌握需要不断地练习和总结。最后分享一个小技巧在面试中遇到需要稳定排序的问题首先要想到归并排序。归并排序是一种稳定的排序算法掌握它的实现和原理对于解决稳定排序相关的问题非常有帮助。这就是大佬吗我也要成为这样的人输入输出示例输入输出示例 1输入arr [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] print(merge_sort(arr))输出[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]输入输出示例 2输入arr [5, 4, 3, 2, 1] temp [0] * len(arr) merge_sort_in_place(arr, temp, 0, len(arr) - 1) print(arr)输出[1, 2, 3, 4, 5]结语归并排序是一种高效的稳定排序算法掌握它不仅有助于解决相关的算法问题也能帮助我们更好地理解分治思想。希望这篇文章对大家有所帮助祝大家刷题愉快本文由 cannonjinx 原创转载请注明出处。