【数据结构】排序算法：归并排序与基数排序

考点频率★★★★☆选择题常考归并排序的复杂度与稳定性是重点基数排序常考其适用场景难度⭐⭐⭐⭐归并排序需理解分治与合并基数排序需理解分配与收集过程建议重点掌握归并排序的“分治合并”思想及时间复杂度重点掌握基数排序的LSD过程及适用场景1️⃣ 为什么还有这两种排序前面我们学过了插入类插入排序、交换类冒泡、快速、选择类简单选择、堆排序。这些排序算法有一个共同特点它们都基于“比较”——通过比较元素的大小来决定位置。而归并排序和基数排序代表了两种完全不同的思路算法核心策略一句话概括归并排序分治先分割成小块排序后再合并“先分后合分而治之”基数排序不比较大小按位分配“按位分配逐位收集”打个比方归并排序像整理一份打乱的文件——先把文件分成两半分别整理好再把两半合并成一份有序的整体。基数排序像按电话号码排序——先按最后一位分到10个桶里再按倒数第二位分……经过所有位数后自然就有序了全程不需要比较大小。2️⃣ 归并排序Merge Sort2.1 核心思想归并排序采用分治Divide and Conquer策略分将待排序序列从中间一分为二递归地对左右两部分进行归并排序治当子序列长度为1时递归返回合将两个已排序的子序列合并成一个有序序列打个比方你有一副打乱顺序的扑克牌。你把牌分成两堆分别整理成有序的然后再把两堆牌合并成一堆有序的牌。这个过程就像“分而治之”——先分后合。2.2 合并两个有序数组核心操作归并排序的核心操作是合并两个已经有序的子序列。左子序列 [1, 3, 5, 7] 右子序列 [2, 4, 6, 8] 合并过程 1. 比较1和2 → 取1 2. 比较3和2 → 取2 3. 比较3和4 → 取3 4. 比较5和4 → 取4 5. 比较5和6 → 取5 6. 比较7和6 → 取6 7. 比较7和8 → 取7 8. 取8 合并结果 [1, 2, 3, 4, 5, 6, 7, 8]2.3 执行过程示例对数组[5, 3, 8, 1, 4, 7, 2, 6]进行归并排序[5, 3, 8, 1, 4, 7, 2, 6] / \ [5, 3, 8, 1] [4, 7, 2, 6] / \ / \ [5, 3] [8, 1] [4, 7] [2, 6] / \ / \ / \ / \ [5] [3] [8] [1] [4] [7] [2] [6] \ / \ / \ / \ / [3, 5] [1, 8] [4, 7] [2, 6] \ / \ / [1, 3, 5, 8] [2, 4, 6, 7] \ / [1, 2, 3, 4, 5, 6, 7, 8]2.4 复杂度与特点情况时间复杂度说明最好情况O(nlog⁡n)O(n \log n)O(nlogn)与初始顺序无关最坏情况O(nlog⁡n)O(n \log n)O(nlogn)与初始顺序无关平均情况O(nlog⁡n)O(n \log n)O(nlogn)与初始顺序无关空间复杂度O(n)O(n)O(n)合并时需要额外的数组空间稳定性✅稳定合并时相等元素保持原有顺序3️⃣ 基数排序Radix Sort3.1 核心思想基数排序不基于比较而是基于分配和收集。它将整数按位数个位、十位、百位……进行多趟排序。打个比方你要按学号给同学排序。你不需要比较学号的大小而是先按最后一位数字分到10个组里分配按顺序收集起来收集再按倒数第二位数字分组收集……经过所有位数后学号自然就有序了。两种实现方式方式说明软考重点最高位优先MSD从最高位开始分配较少考查最低位优先LSD从最低位开始分配软考重点LSD的实现更简单也是软考中最常考的方式。3.2 基数排序的LSD过程步骤确定最大数的位数ddd对i0i 0i0到d−1d-1d−1分配根据第iii位的数字0-9将元素放入对应的10个桶中收集按桶的顺序0→1→2→…→9依次取出元素示例对[329, 457, 657, 839, 436, 720, 355]进行基数排序LSD第1趟按个位分配桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9720————355436457,657—329,839收集后[720, 355, 436, 457, 657, 329, 839]第2趟按十位分配桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9——329436—457,657————720———839—————收集后[720, 329, 436, 839, 355, 457, 657]第3趟按百位分配桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9———329,355436,457—657720——收集后[329, 355, 436, 457, 657, 720, 839]3.3 复杂度与特点情况时间复杂度说明最好情况O(d×(nr))O(d \times (n r))O(d×(nr))ddd为位数rrr为基数通常为10最坏情况O(d×(nr))O(d \times (n r))O(d×(nr))与初始顺序无关平均情况O(d×(nr))O(d \times (n r))O(d×(nr))与初始顺序无关空间复杂度O(nr)O(n r)O(nr)需要桶的空间稳定性✅稳定分配收集不改变同值元素的顺序关键特点基数排序的复杂度与初始序列是否有序无关适用于整数、字符串等固定位数的数据当ddd较小时效率很高如身份证号、学号4️⃣ 八大排序算法全景对比必背总结表算法最好最坏平均空间稳定性是否原地插入排序O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)✅ 稳定✅ 是冒泡排序O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)✅ 稳定✅ 是简单选择O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)❌ 不稳定✅ 是快速排序O(nlog⁡n)O(n \log n)O(nlogn)O(n2)O(n^2)O(n2)O(nlog⁡n)O(n \log n)O(nlogn)O(log⁡n)O(\log n)O(logn)❌ 不稳定✅ 是堆排序O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(1)O(1)O(1)❌ 不稳定✅ 是归并排序O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(n)O(n)O(n)✅ 稳定❌ 否希尔排序O(n1.3)O(n^{1.3})O(n1.3)O(n2)O(n^2)O(n2)O(nlog⁡n)O(n \log n)O(nlogn)~O(n2)O(n^2)O(n2)O(1)O(1)O(1)❌ 不稳定✅ 是基数排序O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(nr)O(nr)O(nr)✅ 稳定❌ 否5️⃣ 经典例题例题1归并排序过程对序列[6, 2, 8, 1, 5, 3]进行归并排序写出第一次合并后的结果。解析分[6, 2, 8]和[1, 5, 3]继续分[6] [2, 8]和[1] [5, 3]继续分[6] [2] [8]和[1] [5] [3]合并相邻[2, 6] [1, 8]和[1, 5] [3]再合并[1, 2, 6, 8]和[1, 3, 5]最终合并[1, 1, 2, 3, 5, 6, 8]第一次合并后的结果是[2, 6] [1, 8] [1, 5] [3]。答案[2, 6, 1, 8, 1, 5, 3]例题2基数排序适用场景以下哪种数据最适合用基数排序A. 100个随机浮点数B. 10000个学生的学号8位数字C. 10000个随机字符串长度不等D. 100个结构体对象解析基数排序适合固定长度的数据如学号、身份证号、IP地址。A浮点数处理复杂C长度不等需要特殊处理D结构体需按特定关键字排序。B学号是固定8位数字最适合基数排序。选B。例题3判断归并排序的平均时间复杂度为O(n2)O(n^2)O(n2)。 解析错误。归并排序的平均时间复杂度为O(nlog⁡n)O(n \log n)O(nlogn)。6️⃣ 记忆口诀归并排序分治精先分后合两路行。O(nlog⁡n)O(n \log n)O(nlogn)稳定排空间O(n)O(n)O(n)要记清。基数排序不比较按位分配逐位收。ddd趟收集nrnrnr固定长度最优解。7️⃣ 小测验评论区对答案对序列[4, 2, 7, 1, 9, 5]进行归并排序合并过程中最后一轮合并时左右两个子序列分别是 。A.[2, 4, 7]和[1, 5, 9]B.[1, 2, 4, 7]和[5, 9]C.[2, 4, 7]和[1, 5, 9]D.[1, 2, 4, 5, 7, 9]本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #归并排序 #基数排序 #排序算法 #数据结构 #软考备考