当前位置：首页 > news >正文

【排序 - 归并排序】

news 2025/7/18 22:36:15

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

归并排序的原理

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

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

归并排序的算法步骤

分解：
- 将待排序数组分为两个大致相等的子数组。
- 递归地对每个子数组进行归并排序，直到子数组长度为1。
合并：
- 合并两个已排序的子数组为一个新的有序数组。
- 将两个子数组的元素逐个比较，依次放入新数组中，直到将两个子数组全部合并。
递归结束条件：
- 当子数组长度为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;
}