算法笔记--归并排序

小编 2026-06-10 阅读:1354 评论:0

归并排序是一种使用分治策略的排序算法，适用于待排序列整体无序、部分有序的情况。1. 算法思想 ...

归并排序是一种使用分治策略的排序算法，适用于待排序列整体无序、部分有序的情况。

1. 算法思想

递归地将待排序列等分为两个子序列，直到子序列有序（狭义得讲就是只有一个元素），再将两个子序列合并为一个新的有序序列。

2. 时间复杂度

最好情况 O(nlogn)：用递归树思想，每次递归划分合并总共都需处理n个元素，共递归划分了logn次

最坏情况 O(nlogn)：对数据顺序不敏感

3. 空间复杂度 O(n)

需要额外的空间暂存新合并的有序序列

4. 稳定性

稳定。相邻序列合并，不改变同值元素的原始顺序

5. 代码实现（C语言）

首先看一下入口函数，这里创建了一个大小为n的数值，用于保存中间归并的有序序列：

void MergeSort(int *A, int n){	int *L = (int *)malloc(n * sizeof(int));	MSort(A, L, 0, n - 1);	free(L);}

然后是归并排序递归处理子序列的过程：

void MSort(int *A, int *L, int low, int high){	int mid;	if (low < high)	{		mid = (low + high) / 2;		MSort(A, L, low, mid);		MSort(A, L, mid + 1, high);		Merge(A, L, low, high);	}}

最后是合并两个子序列的函数：

void Merge(int *A, int *L, int low, int high){	int i, j, k;	int mid = (low + high) / 2;	if (low >= high)	{		return;	}	i = low;	j = mid + 1;	k = 0;	while (i <= mid && j <= high)	{		if (A[i] <= A[j])		{			L[k++] = A[i++];		}		else		{			L[k++] = A[j++];		}	}	while (i <= mid)	{		L[k++] = A[i++];	}	while (j <= high)	{		L[k++] = A[j++];	}	for (i = low; i <= high; ++i)	{		A[i] = L[i - low];	}}

注：将子序列划分到只有一个元素为止不是好的做法，可以在子序列元素个数小于10时，使用直接选择排序处理子序列，这样能提升排序效率。