归并排序的一些介绍

发布于:2025-03-17 ⋅ 阅读:(17) ⋅ 点赞:(0)

归并排序(Merge Sort)是一种基于分治法(Divide and Conquer)的排序算法。它的核心思想是将数组分成两个子数组,分别对子数组进行排序,然后将排序后的子数组合并成一个有序的数组。归并排序的时间复杂度为 𝑂(𝑛log⁡𝑛)O(nlogn),是一种稳定的排序算法。

归并排序的步骤:

  1. 分解:将数组从中间分成两个子数组,递归地对每个子数组进行排序。

  2. 合并:将两个已排序的子数组合并成一个有序的数组。

算法实现:

#include<stdio.h>
#include<stdlib.h>
void print_arr(int arr[], int n)
{
	for (int i = 0;i < n;i++)
	{
		printf("%d ", arr[i]);
	}
	pritnf('\n');
}
//归并排序
void msort(itn arr[], itn tempArr[], int left, int right)
{
	//如果只有一个元素,那么就不用被继续划分
	//只有一个元素的区域,本身就是有序的,只需要被归并即可。
	if (left < right)
	{
		int mid = (left + right) / 2;
		//递归划分左半区
		msort(arr, tempArr, left, mid);
		//递归划分右半区
		msort(arr, tempArr, mid + 1, right);
		//合并已经排序的部分
		merge(arr, tempArr, left, mid, right);
	}
}
//合并
void merge(int arr[],int tempArr, int left,int mid,int right)
{
	//标记左半区第一个未排序的元素
	int l_pos = left;
	//标记右半区第一个未排序的元素
	int r_pos = mid + 1;
	//临时数组元素的下标
	int pos=left;
	//合并
	while (l_pos <= mid && r_pos <= right)
	{
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}
	//合并左半区剩余的元素
	while (l_pos <= mid)
	{
		tempArr[pos++] = arr[l_pos++];
	}
	//合并右半区剩余的元素
	while (l_pos <= right)
	{
		tempArr[pos++] = arr[l_pos++];
	}
	//把临时数组中合并后的元素复制回原来的数组
	while (left <= right)
	{
		arr[left] = tempArr[left];
		left++;
	}
}
//归并排序入口
void merge_sort(int arr[], int n)
{
	//分配一个辅助的数组
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr)
	{
		msort(arr, tempArr, 0, n - 1);
		free(tempArr);
	}
	else
	{
		printf("error:failed to allocate memory");
	}
}
int main()
{
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int n = 9;
	print_arr(arr, n);
	merge_sort(arr, n);
	print_arr(arr, n);
	return 0;
}

时间复杂度:

  • 分解:每次将数组分成两半,需要 𝑂(log⁡𝑛)O(logn) 次分解。

  • 合并:每次合并操作需要 𝑂(𝑛)O(n) 的时间。

  • 总时间复杂度为 𝑂(𝑛log⁡𝑛)O(nlogn)。

空间复杂度:

  • 归并排序需要额外的空间来存储合并后的数组,空间复杂度为 𝑂(𝑛)O(n)

稳定性:

  • 归并排序是稳定的排序算法,因为在合并过程中,相等元素的相对顺序不会改变

适用场景:

  • 归并排序适用于需要稳定排序的场景,尤其是对链表进行排序时,归并排序的空间复杂度可以优化为 𝑂(1)O(1)