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

归并排序详解

ai 2025/7/4 6:01:09

创建两个临时数组存储待合并的子数组

使用双指针法依次比较两个子数组的元素

将较小的元素放入原数组的对应位置

处理剩余未合并的元素

前言

1. 算法概述

归并排序是一种采用分治法（Divide and Conquer）策略的排序算法，由约翰·冯·诺伊曼在1945年提出。它的核心思想是将一个大问题分解成若干个小问题，递归解决小问题后，再将结果合并起来。

分治策略

分解：将当前区间一分为二解决：递归地对两个子区间进行排序合并：将两个已排序的子区间合并成一个有序区间

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 = (int *)malloc(n1 * sizeof(int));int *R = (int *)malloc(n2 * sizeof(int));// 拷贝数据到临时数组for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];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++;}// 拷贝剩余元素（如果有）while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}free(L);free(R);
}
void  sort(int arr[],int left,int right)
{if(left<right){int mid=left+(right-left)/2;sort(arr,left,mid)sort(arr,mid+1,right);merge(arr,left,mid,right);}
}
// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}
// 测试代码
int main() {int arr[] = {38, 27, 43, 3};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;
}

初始调用：mergeSort(arr, 0, 3)mid = 1递归左：mergeSort(arr, 0, 1)mid = 0递归左：mergeSort(arr, 0, 0) → 直接返回递归右：mergeSort(arr, 1, 1) → 直接返回merge([38,27], 0, 0, 1) → 变为 [27, 38]递归右：mergeSort(arr, 2, 3)mid = 2递归左：mergeSort(arr, 2, 2) → 直接返回递归右：mergeSort(arr, 3, 3) → 直接返回merge([43,3], 2, 2, 3) → 变为 [3, 43]merge([27,38,3,43], 0, 1, 3) → 最终 [3, 27, 38, 43]

可能的优化

小数组优化：当子数组较小时（如 <15个元素），改用插入排序避免重复分配内存：预先分配临时缓冲区自底向上实现：使用迭代代替递归减少调用开销

与其他排序算法比较

特性	归并排序	快速排序	堆排序
时间复杂度	O(n log n)	O(n log n)	O(n log n)
空间复杂度	O(n)	O(log n)	O(1)
稳定性	稳定	不稳定	不稳定
适用性	通用	通用	通用
最佳场景	大数据/外部排序	内存中小数据集	内存受限环境