归并排序算法c语言

<think>我们被要求使用C语言实现归并排序算法。根据引用内容，归并排序有两种实现方式：递归和非递归。我们将分别展示这两种实现，并解释其原理。 ### 归并排序原理 归并排序采用分治法（Divide and Conquer）： 1. **分**：将数组分成两个子数组，然后递归地对子数组进行排序。 2. **治**：将两个已排序的子数组合并成一个有序数组。 递归实现是自顶向下的，而非递归实现是自底向上的。 ### 递归实现 引用[1]和[2]提供了递归实现的代码。我们整合并优化代码，注意避免全局数组，使用临时数组。 ```c #include <stdio.h> #include <stdlib.h> // 合并两个有序数组 void merge(int arr[], int left, int mid, int right, int temp[]) { int i = left; // 左数组起始索引 int j = mid + 1; // 右数组起始索引 int k = 0; // 临时数组索引 // 合并直到其中一个数组结束 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++]; } // 将临时数组复制回原数组 k = 0; while (left <= right) { arr[left++] = temp[k++]; } } // 归并排序递归函数 void mergeSortRecursive(int arr[], int left, int right, int temp[]) { if (left >= right) { return; } int mid = left + (right - left) / 2; // 避免溢出 mergeSortRecursive(arr, left, mid, temp); mergeSortRecursive(arr, mid + 1, right, temp); merge(arr, left, mid, right, temp); } // 归并排序入口 void mergeSort(int arr[], int n) { int* temp = (int*)malloc(n * sizeof(int)); if (temp == NULL) { perror("malloc fail"); exit(-1); } mergeSortRecursive(arr, 0, n - 1, temp); free(temp); } // 测试 int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); mergeSort(arr, n); printf("排序后数组: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } ``` ### 非递归实现 引用[1]提到了非递归实现，但没有给出代码。非递归实现使用循环，从最小子数组（大小为1）开始合并，逐步扩大。 ```c #include <stdio.h> #include <stdlib.h> // 合并函数（同上） void merge(int arr[], int left, int mid, int right, int temp[]) { // ... 同上 ... } // 归并排序非递归实现 void mergeSortIterative(int arr[], int n) { int* temp = (int*)malloc(n * sizeof(int)); if (temp == NULL) { perror("malloc fail"); exit(-1); } // 初始子数组大小为1，然后倍增 for (int size = 1; size < n; size *= 2) { // 每次步进2*size for (int left = 0; left < n; left += 2 * size) { int mid = left + size - 1; if (mid >= n - 1) { // 如果mid超出范围，说明没有右数组，无需合并 break; } int right = (left + 2 * size - 1) < (n - 1) ? (left + 2 * size - 1) : (n - 1); merge(arr, left, mid, right, temp); } } free(temp); } // 测试（同上，只需将mergeSort改为mergeSortIterative） ``` ### 关键点解释 1. **递归实现**：通过递归将数组不断二分，直到子数组大小为1，然后合并。 2. **非递归实现**：使用循环，从大小为1的子数组开始，两两合并，每次合并后子数组大小翻倍。 3. **合并操作**：是归并排序的核心，需要额外空间（临时数组）来合并两个有序数组。 ### 性能分析 - 时间复杂度：$O(n \log n)$，因为每次合并操作是$O(n)$，而分治的深度是$O(\log n)$。 - 空间复杂度：$O(n)$，因为需要与原始数组同样大小的临时空间。 ### 优化 1. 当子数组较小时，可以使用插入排序（因为小数组插入排序可能更快）。 2. 检查数组是否已经有序，避免不必要的合并。 3. 非递归实现避免了递归调用的开销，且是稳定的排序算法。 ### 应用场景 归并排序适用于需要稳定排序（相同元素顺序不变）的场景，也适合链表排序（因为不需要随机访问）以及外部排序（数据量大，无法全部放入内存）。 §§相关问题§§ 1. 归并排序的递归和非递归实现在性能上有什么区别？ 2. 如何优化归并排序以减少空间使用？ 3. 归并排序在什么情况下会退化为$O(n^2)$时间复杂度？</think>### 归并排序算法详解（C语言实现） 归并排序是一种基于**分治法**的高效排序算法，其核心思想是将数组递归拆分为最小单元（单个元素），再逐步合并有序子数组。时间复杂度为 $O(n \log n)$，空间复杂度 $O(n)$，是**稳定排序算法**。 --- #### 递归实现（自顶向下） ```c #include <stdio.h> #include <stdlib.h> // 合并两个有序数组 void merge(int arr[], int left, int mid, int right, int temp[]) { int i = left; // 左子数组起始位置 int j = mid + 1; // 右子数组起始位置 int k = 0; // 临时数组索引 // 比较左右子数组元素，按序存入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++]; // 将temp数据复制回原数组 for (int m = 0; m < k; m++) arr[left + m] = temp[m]; } // 递归拆分与合并 void mergeSortRecursive(int arr[], int left, int right, int temp[]) { if (left >= right) return; // 递归终止条件 int mid = left + (right - left) / 2; // 防溢出计算中点 mergeSortRecursive(arr, left, mid, temp); // 左半排序 mergeSortRecursive(arr, mid + 1, right, temp); // 右半排序 merge(arr, left, mid, right, temp); // 合并有序子数组 } // 入口函数 void mergeSort(int arr[], int n) { int* temp = (int*)malloc(n * sizeof(int)); // 申请临时空间 if (temp == NULL) { perror("内存分配失败"); exit(EXIT_FAILURE); } mergeSortRecursive(arr, 0, n - 1, temp); free(temp); // 释放临时空间 } // 测试代码 int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, n); printf("排序结果: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); // 输出: 5 6 7 11 12 13 return 0; } ``` --- #### 非递归实现（自底向上） ```c void mergeSortIterative(int arr[], int n) { int* temp = (int*)malloc(n * sizeof(int)); if (temp == NULL) exit(EXIT_FAILURE); for (int size = 1; size < n; size *= 2) { // 子数组大小倍增 for (int left = 0; left < n - 1; left += 2 * size) { int mid = left + size - 1; int right = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1; merge(arr, left, mid, right, temp); // 合并相邻子数组 } } free(temp); } ``` --- ### 关键点解析 1. **分治策略**： - **分**：递归将数组二分至单个元素（天然有序）。 - **治**：合并两个有序子数组，通过临时数组比较元素顺序。 2. **稳定性**： - 合并时 `arr[i] <= arr[j]` 保证相等元素的原始顺序不变[^3]。 3. **空间复杂度**： - 需 $O(n)$ 临时空间存储合并结果，是非原地排序。 4. **适用场景**： - 大数据量排序（时间复杂度稳定为 $O(n \log n)$）。 - 链表排序（无需随机访问）。 - 外部排序（数据量超过内存容量）[^3]。 --- ### 性能对比 | 实现方式 | 优点 | 缺点 | |------------|--------------------------|----------------------| | 递归 | 代码简洁，逻辑清晰 | 递归栈消耗额外内存 | | 非递归 | 无递归开销，适合大数据量 | 代码复杂度较高 | > **提示**：实际应用中可结合插入排序优化——当子数组长度较小时（如 ≤ 64），使用插入排序减少递归开销[^1]。