排序算法之归并排序

先看一下下面这张图

下面分析归并排序：

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

归并排序的时间复杂度为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
}