排序算法之归并排序

先看一下下面这张图


下面分析归并排序:

归并排序把数组划分成几个小数组,然后小数组成划分,直到每个数组都只有一个元素,然后将相邻的两个数组进行合并,再将合并后的数组继续合并,直到合并成一个数组。总体的思想是先拆分再合并。

归并排序的时间复杂度为O(nlogn)。

由于合并的时候需要额外的一个数组来保存,因此空间复杂度为O(n)。

归并排序合并的时候是相邻的数组进行合并,因此是稳定的。

归并排序可用递归实现,先递归将数组拆分,拆到最小时返回,然后将拆分的两个数组进行合并。

C++代码

/*
* 归并排序
* 先将数组拆分成小数组,然后在合并成大数组
* 合并的时候进行排序,使用一个辅助的空间来存储排好序的元素
* O(nlogn)
* O(n)
* 稳定
*/
#define RECURSION 0
template <typename T>
void SortHelp<T>::mergeSort(T l[], int length) {
#ifdef RECURSION
	//使用递归
	merge(l, 0, length - 1);
#else

#endif // RECURSION
}

template<typename T>
void SortHelp<T>::merge(T l[], int start, int end)
{
	//数组只剩下一个元素
	if (start == end)
	{
		return;
	}

	int mid = (start + end) / 2;
	merge(l, start, mid);
	merge(l, mid + 1, end);

	//合并两个数组
	T* temp = (T*)malloc(sizeof(T)*(end - start + 1));
	int i, j, k;
	for (i = start, j = mid + 1, k = 0; i <= mid && j <= end; k++)
	{
		if (l[i] < l[j])
		{
			temp[k] = l[i];
			i++;
		}
		else
		{
			temp[k] = l[j];
			j++;
		}
	}
	while (i <= mid)
	{
		temp[k++] = l[i++];
	}
	while (j <= end)
	{
		temp[k++] = l[j++];
	}
	//复制回原数组
	for (i = start, k = 0; i <= end; i++)
	{
		l[i] = temp[k++];
	}
}

也可以不使用递归,不用拆分,直接从最小单位开始合并,合并完一趟后把合并单位翻倍。

C++代码

/*
* 归并排序
* 先将数组拆分成小数组,然后在合并成大数组
* 合并的时候进行排序,使用一个辅助的空间来存储排好序的元素
* O(nlogn)
* O(n)
* 稳定
*/
//#define RECURSION 0
template <typename T>
void SortHelp<T>::mergeSort(T l[], int length) {
#ifdef RECURSION
	//使用递归
	merge(l, 0, length - 1);
#else
	//不使用递归
	int dt = 1;

	T* temp = (T*)malloc(sizeof(T)*length);
	int i, j, k;

	while (dt < length)
	{
		for (int s = 0; s < length; s += 2 * dt)
		{
			//合并数组[s,s+dt-1]和数组[s+dt,s+2dt-1]
			for (i = s, j = s + dt, k = 0; i < s + dt && j < s + 2 * dt && j < length; k++)
			{
				if (l[i] < l[j])
				{
					temp[k] = l[i++];
				}
				else
				{
					temp[k] = l[j++];
				}
			}
			while (i < s + dt)
			{
				temp[k++] = l[i++];
			}
			while (j < s + 2 * dt && j < length)
			{
				temp[k++] = l[j++];
			}
			//复制回源数组
			for (i = s, k = 0; i < s + 2 * dt && i < length; i++, k++)
			{
				l[i] = temp[k];
			}
		}
		dt *= 2;
	}
	free(temp);
#endif // RECURSION
}

总结,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n),稳定。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值