【排序 - 归并排序】

归并排序（Merge Sort）是一种高效的排序算法，基于分治（Divide and Conquer）策略。它将待排序数组分成两个较小的子数组，分别对它们进行排序，然后将排好序的子数组合并成一个整体有序的数组。归并排序的时间复杂度为O(n log n)，在大多数情况下是最佳选择之一。

归并排序的原理

归并排序的过程可以分为两个主要步骤：分解和合并。

1. 分解：将原始数组递归地分解为较小的子数组，直到每个子数组只有一个元素。
2. 合并：将两个已排序的子数组合并成一个有序的数组，不断重复这个过程直到整个数组排序完成。
   

归并排序的算法步骤

1. 分解：

   • 将待排序数组分为两个大致相等的子数组。
   • 递归地对每个子数组进行归并排序，直到子数组长度为1。

2. 合并：

   • 合并两个已排序的子数组为一个新的有序数组。
   • 将两个子数组的元素逐个比较，依次放入新数组中，直到将两个子数组全部合并。

3. 递归结束条件：

   • 当子数组长度为1时，递归结束。

归并排序的C语言实现

下面是归并排序的C语言实现示例：

#include <stdio.h>
#include <stdlib.h>// 归并函数，用于将两个已排序的数组合并为一个有序数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;    // 左子数组的大小int n2 = right - mid;       // 右子数组的大小// 创建临时数组int L[n1], R[n2];// 将数据复制到临时数组 L[] 和 R[] 中for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 归并临时数组到 arr[left..right]i = 0;  // 初始化左子数组的索引j = 0;  // 初始化右子数组的索引k = left;  // 初始化归并子数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制 L[] 的剩余元素（如果有）while (i < n1) {arr[k] = L[i];i++;k++;}// 复制 R[] 的剩余元素（如果有）while (j < n2) {arr[k] = R[j];j++;k++;}
}// 归并排序函数
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;  // 避免溢出mergeSort(arr, left, mid);   // 对左半部分进行归并排序mergeSort(arr, mid + 1, right);  // 对右半部分进行归并排序merge(arr, left, mid, 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[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);printf("原始数组:\n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf("排序后的数组:\n");printArray(arr, arr_size);return 0;
}

总结

归并排序是一种效率高且稳定的排序算法，适用于大规模数据集的排序需求。通过递归地分解和合并数组，归并排序可以在O(n log n)的时间复杂度内完成排序，因此在实际应用中被广泛使用。通过本文的介绍和C语言实现示例，读者可以更深入地理解归并排序的工作原理和实现方式。