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

目录一、归并排序1.1 算法思想1.2 图解示例1.3 合并过程详解1.4 代码实现二、归并排序的复杂度分析2.1 时间复杂度2.2 空间复杂度2.3 稳定性三、归并排序的性能测试四、基数排序4.1 算法思想4.2 LSD最低位优先4.3 LSD代码实现五、基数排序的优化与变体5.1 MSD最高位优先5.2 LSD vs MSD六、基数排序的复杂度分析6.1 时间复杂度6.2 空间复杂度6.3 适用场景七、三种排序算法对比八、完整性能测试九、小结十、思考题一、归并排序1.1 算法思想归并排序采用分治策略分解将数组分成两半解决递归地对两半进行归并排序合并将两个有序子数组合并成一个有序数组1.2 图解示例text初始: [5, 2, 4, 6, 1, 3] 分解 [5,2,4] [6,1,3] [5,2] [4] [6,1] [3] [5][2] [6][1] 合并 [2,5] [4] → [2,4,5] [1,6] [3] → [1,3,6] 最终合并[1,2,3,4,5,6]1.3 合并过程详解合并两个有序数组[2,4,5]和[1,3,6]text比较2和1 → 取1 → [1] 比较2和3 → 取2 → [1,2] 比较4和3 → 取3 → [1,2,3] 比较4和6 → 取4 → [1,2,3,4] 比较5和6 → 取5 → [1,2,3,4,5] 剩余6 → [1,2,3,4,5,6]1.4 代码实现c#include stdio.h #include stdlib.h #include string.h #include time.h // 合并两个有序子数组 [left, mid] 和 [mid1, right] void merge(int arr[], int left, int mid, int right, int temp[]) { int i left; // 左子数组起始 int j mid 1; // 右子数组起始 int k left; // 临时数组索引 // 比较两个子数组取较小者放入temp while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 复制剩余元素 while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } // 将临时数组复制回原数组 for (i left; i right; i) { arr[i] temp[i]; } } // 归并排序递归实现 void mergeSort(int arr[], int left, int right, int temp[]) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } // 归并排序入口 void mergeSortWrapper(int arr[], int n) { int *temp (int*)malloc(n * sizeof(int)); mergeSort(arr, 0, n - 1, temp); free(temp); } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 4, 6, 1, 3}; int n sizeof(arr) / sizeof(arr[0]); printf(原数组: ); printArray(arr, n); mergeSortWrapper(arr, n); printf(排序后: ); printArray(arr, n); return 0; }运行结果text原数组: 5 2 4 6 1 3 排序后: 1 2 3 4 5 6二、归并排序的复杂度分析2.1 时间复杂度归并排序的时间复杂度是稳定的 O(n log n)text递推式T(n) 2T(n/2) O(n) 解得T(n) O(n log n)情况时间复杂度最好O(n log n)最坏O(n log n)平均O(n log n)2.2 空间复杂度归并排序需要 O(n) 的额外空间来存储临时数组。text每层递归需要 O(n) 的临时空间 递归深度为 O(log n) 但同一时间只使用一份临时数组所以总空间为 O(n)2.3 稳定性归并排序是稳定排序。在合并时当左右元素相等时先取左边的保证了稳定性。三、归并排序的性能测试cvoid testMergeSortPerformance() { srand(time(NULL)); int sizes[] {1000, 10000, 50000, 100000}; int nTests sizeof(sizes) / sizeof(sizes[0]); printf( 归并排序性能测试 \n); for (int t 0; t nTests; t) { int n sizes[t]; int *arr (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) { arr[i] rand() % 10000; } clock_t start clock(); mergeSortWrapper(arr, n); clock_t end clock(); double time (double)(end - start) / CLOCKS_PER_SEC * 1000; printf(n%d: %.2f ms\n, n, time); free(arr); } }运行结果示例text 归并排序性能测试 n1000: 0.25 ms n10000: 2.18 ms n50000: 12.45 ms n100000: 26.83 ms四、基数排序4.1 算法思想基数排序不比较元素大小而是按位分配将整数按某一位个位、十位...分配到0-9的桶中按桶顺序收集重复处理下一位4.2 LSD最低位优先从个位开始依次向高位处理。示例[170, 45, 75, 90, 2, 802, 24, 66]text按个位分配 桶0: 170, 90 桶2: 2, 802 桶4: 24 桶5: 45, 75 桶6: 66 收集170, 90, 2, 802, 24, 45, 75, 66 按十位分配 桶0: 2, 802 桶2: 24 桶4: 45 桶6: 66 桶7: 170, 75 桶9: 90 收集2, 802, 24, 45, 66, 170, 75, 90 按百位分配 桶0: 2, 24, 45, 66, 75, 90 桶1: 170 桶8: 802 收集2, 24, 45, 66, 75, 90, 170, 802 排序完成4.3 LSD代码实现c#include stdio.h #include stdlib.h #include string.h // 获取数字的第d位d0表示个位 int getDigit(int num, int d) { for (int i 0; i d; i) { num / 10; } return num % 10; } // LSD基数排序 void radixSortLSD(int arr[], int n) { if (n 0) return; // 1. 找到最大值确定位数 int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) max arr[i]; } int maxDigits 0; while (max 0) { maxDigits; max / 10; } // 2. 分配桶10个桶每个桶最多n个元素 int **buckets (int**)malloc(10 * sizeof(int*)); int *bucketSizes (int*)calloc(10, sizeof(int)); for (int i 0; i 10; i) { buckets[i] (int*)malloc(n * sizeof(int)); } // 3. 对每一位进行分配和收集 for (int d 0; d maxDigits; d) { // 重置桶大小 for (int i 0; i 10; i) { bucketSizes[i] 0; } // 分配将元素放入对应桶 for (int i 0; i n; i) { int digit getDigit(arr[i], d); buckets[digit][bucketSizes[digit]] arr[i]; } // 收集按桶顺序取回元素 int index 0; for (int i 0; i 10; i) { for (int j 0; j bucketSizes[i]; j) { arr[index] buckets[i][j]; } } } // 释放内存 for (int i 0; i 10; i) { free(buckets[i]); } free(buckets); free(bucketSizes); } // 打印数组 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {170, 45, 75, 90, 2, 802, 24, 66}; int n sizeof(arr) / sizeof(arr[0]); printf(原数组: ); printArray(arr, n); radixSortLSD(arr, n); printf(排序后: ); printArray(arr, n); return 0; }运行结果text原数组: 170 45 75 90 2 802 24 66 排序后: 2 24 45 66 75 90 170 802五、基数排序的优化与变体5.1 MSD最高位优先从高位开始分配适用于字符串排序可以提前终止。c// MSD基数排序递归处理范围[lo, hi]当前位d void radixSortMSD(int arr[], int lo, int hi, int d, int maxDigits) { if (lo hi || d maxDigits) return; int buckets[10] {0}; int *temp (int*)malloc((hi - lo 1) * sizeof(int)); // 统计每个桶的大小 for (int i lo; i hi; i) { int digit getDigit(arr[i], maxDigits - 1 - d); buckets[digit]; } // 计算桶的起始位置 int start[10]; start[0] 0; for (int i 1; i 10; i) { start[i] start[i - 1] buckets[i - 1]; } // 分配 for (int i lo; i hi; i) { int digit getDigit(arr[i], maxDigits - 1 - d); temp[start[digit]] arr[i]; } // 复制回原数组 for (int i 0; i hi - lo 1; i) { arr[lo i] temp[i]; } // 递归处理每个桶 int pos lo; for (int i 0; i 10; i) { if (buckets[i] 0) { radixSortMSD(arr, pos, pos buckets[i] - 1, d 1, maxDigits); pos buckets[i]; } } free(temp); }5.2 LSD vs MSD对比项LSDMSD处理顺序个位→十位→百位百位→十位→个位实现方式迭代递归空间复杂度O(n)O(n)适用场景整数、定长字符串变长字符串可提前终止稳定性稳定稳定六、基数排序的复杂度分析6.1 时间复杂度对 d 位数字每位需要 O(n) 的分配和收集总时间复杂度O(d × n)对于32位整数d10十进制或 d32二进制即 O(n)6.2 空间复杂度需要 O(n k) 的额外空间k10桶的数量6.3 适用场景优点缺点时间复杂度 O(n)只能用于整数或字符串稳定排序需要额外空间适合大数据量对负数处理较麻烦七、三种排序算法对比算法时间复杂度空间复杂度稳定性是否比较归并排序O(n log n)O(n)稳定是基数排序O(d×n)O(nk)稳定否快速排序O(n log n)O(log n)不稳定是八、完整性能测试c#include stdio.h #include stdlib.h #include time.h // 归并排序略见上文 // 基数排序略见上文 // 快速排序简单实现 void quickSort(int arr[], int left, int right) { if (left right) return; int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; quickSort(arr, left, i - 1); quickSort(arr, i 1, right); } void testAllSorts() { srand(time(NULL)); int n 50000; int *arr1 (int*)malloc(n * sizeof(int)); int *arr2 (int*)malloc(n * sizeof(int)); int *arr3 (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) { int val rand() % 100000; arr1[i] arr2[i] arr3[i] val; } clock_t start, end; start clock(); mergeSortWrapper(arr1, n); end clock(); printf(归并排序: %.2f ms\n, (double)(end - start) / CLOCKS_PER_SEC * 1000); start clock(); quickSort(arr2, 0, n - 1); end clock(); printf(快速排序: %.2f ms\n, (double)(end - start) / CLOCKS_PER_SEC * 1000); start clock(); radixSortLSD(arr3, n); end clock(); printf(基数排序: %.2f ms\n, (double)(end - start) / CLOCKS_PER_SEC * 1000); free(arr1); free(arr2); free(arr3); } int main() { testAllSorts(); return 0; }运行结果示例text归并排序: 12.45 ms 快速排序: 8.32 ms 基数排序: 6.78 ms九、小结这一篇我们学习了归并排序和基数排序算法核心思想时间复杂度空间复杂度稳定性归并排序分治合并O(n log n)O(n)稳定基数排序按位分配收集O(d×n)O(nk)稳定归并排序要点分治策略先分后合需要 O(n) 额外空间稳定排序适合外部排序基数排序要点非比较排序按位处理LSD从低位到高位MSD从高位到低位时间复杂度 O(n)但常数较大下一篇我们讲排序大总结。十、思考题归并排序的空间复杂度能否优化到 O(1)如何实现为什么归并排序适合外部排序磁盘文件排序基数排序中如果数据包含负数应该如何处理对于字符串数组LSD和MSD哪个更合适为什么欢迎在评论区讨论你的答案。