C语言详解：归并排序原理与实现

归并排序是一种高效的排序算法，它遵循分治策略，通过将原始序列分解成越来越小的子序列，然后递归地对这些子序列进行排序并合并，最后得到完全有序的结果。在C语言中，归并排序的实现主要包括两个主要部分：合并操作（`merge`）和递归排序过程（`mergeSort`）。 首先，`merge`函数是归并排序的核心部分，它接收四个参数：输入数组`arr`、子序列的起始索引`left`、子序列的中间索引`middle`以及结束索引`right`。这个函数首先计算出左右子序列的长度，然后创建两个临时数组`Left`和`Right`，分别存储左右子序列的数据。接着，通过两个指针遍历这两个子序列，根据大小关系依次将元素复制回原数组`arr`，直至其中一个子序列全部复制完毕，最后将剩余元素无序的部分也复制到原数组中。 `mergeSort`函数则是整个归并排序的主体，采用递归的方式进行排序。当输入数组的起始索引`left`小于结束索引`right`时，会先计算出中间索引`middle`，然后对左半部分和右半部分递归调用`mergeSort`进行排序。当子序列足够小，只包含一个元素或为空时，递归终止。当左右子序列都已排序后，调用`merge`函数合并两个子序列，从而完成整个排序过程。 为了便于用户查看排序结果，还有一个辅助函数`printArray`，用于打印整个数组的内容。 以下是详细的C语言归并排序代码： ```c #include<stdio.h> // 合并两个已排序的子序列 void merge(int arr[], int left, int middle, int right) { int i, j, k; int n1 = middle - left + 1; // 左子序列的长度 int n2 = right - middle; // 右子序列的长度 // 创建临时数组存放左右子序列的数据 int Left[n1], Right[n2]; // 将左右子序列的数据复制到临时数组中 for (i = 0; i < n1; i++) { Left[i] = arr[left + i]; } for (j = 0; j < n2; j++) { Right[j] = arr[middle + j + 1]; } i = 0; // 左子序列的索引 j = 0; // 右子序列的索引 k = left; // 原数组的索引 while (i < n1 && j < n2) { if (Left[i] <= Right[j]) { arr[k] = Left[i]; i++; } else { arr[k] = Right[j]; j++; } k++; } // 复制左子序列的剩余元素到原数组中 while (i < n1) { arr[k] = Left[i]; i++; k++; } // 复制右子序列的剩余元素到原数组中 while (j < n2) { arr[k] = Right[j]; j++; k++; } } // 归并排序 void mergeSort(int arr[], int left, int right) { if (left < right) { int middle = left + (right - left) / 2; // 计算中间索引 mergeSort(arr, left, middle); // 对左子序列进行排序 mergeSort(arr, middle + 1, right); // 对右子序列进行排序 merge(arr, left, middle, right); // 合并两个已排序子序列 } } // 打印数组 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d", arr[i]); } printf("\n"); } int main() { int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, size); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); return 0; } ``` 当你运行这段代码时，它将对输入数组进行归并排序，并打印出排序前后的结果。归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)，这是因为每次递归都需要额外的空间来存储子序列。尽管它在处理大数据量时表现优异，但空间需求可能会成为问题，特别是对于内存有限的环境。