开发者社区> 兰亭侠> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

算法笔记--归并排序

简介: 归并排序是一种使用分治策略的排序算法,适用于待排序列整体无序、部分有序的情况。 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时,使用直接选择排序处理子序列,这样能提升排序效率。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法】归并排序
【算法】归并排序
14 0
排序算法:归并排序
排序算法:归并排序
39 0
算法学习笔记之选择排序算法
算法学习笔记之选择排序算法
20 0
归并排序算法
算法导论第二章
45 0
排序算法:归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。
604 0
排序算法笔记说明
<p><span style="white-space:pre"></span>         排序算法相关内容(Java实现)是个人理解并代码实现的常用的内部排序算法,目前包括如下七大算法(暂不包括基数排序):</p> <p>         <strong>直接插入排序、希尔排序、简单选择、堆排、冒泡、快排、归并排序</strong>。</p> <p><span style="w
1260 0
算法笔记--冒泡排序
冒泡排序是一种选择排序,算法简单,在数据基本有序的情况下效率较高。 1. 算法思想           通过无序区中元素相邻元素的比较和交换,使最小的元素如同气泡一般浮动至顶端。 2. 时间复杂度           最好情况 O(n):序列正序有序,外循环只执行一次,内层比较n次,不需移动元素(针对改进版而言)          最坏情况 O(n^2):序列逆序有序,每次比较都需交换两个元素 3. 空间复杂度 O(1)           就地排序,辅助空间为常数级 4. 稳定性           稳定。
827 0
+关注
兰亭侠
云计算领域,具有多年的OpenStack、Kubernetes经验
26
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载