归并排序优化之通过自底向上来完成归并排序

我们大家应该都知道归并排序最简单想到的就是自顶向下，采用递归的方法逐步分解为logn层，然后，对每一层采用归并排序，每一层的时间复杂度为O（n），所以归并排序是时间复杂度为O(nlogn)的一种有效的排序方法。那下面我们就来学习一下归并排序的一种优化——自底向上来完成归并排序

PS:我们这里都是默认由小到大排序

自底向上归并排序过程

我们这里就可以化递归为迭代，来实现算法

tmplate <typename T>
void mergeSortBU(T arr[],int n)
{
	int size,i;
	// size设置每一次分的段的长度，如图中的2个元素为一小段，4个元素为一小段中的2和4
	// i设置每一次归并排序的数组下标的范围
	for(size = 1, size <= n; size+=size ) //让其以2的倍数逐渐增加:2,4,8,16...
	{
		for(i = 0 ; i < n ; i += size + size ) //因为是每次两个小段一合并，所以i的跨度为两个小段的长度		
			__merge(arr, i, i+size-1, i+size+size-1);
//这个函数是说将arr数组中的[i,i+size-1],[i+size,i+size+size-1]	这两部分进行合并
	}
}

template <typename T>

//将arr[l,mid] 和 arr[mid+1,r]两部分进行归并
void __merge(T arr[],int l,int mid,int r)
{
	T aux[r-l+1];
	for(int i = l; i <= r;i++)
		aux[i-l] = arr[i]; //aux是从0开始，而arr是从l开始，所以会有l个偏移

	int i = l,j = mid+1;
	for(int k = l; k<=r; k++ )
	{
		if( i > mid )
		{
			arr[k] = aux[j - l];
			j++;
		}
		else if( j > r)
		{
			arr[k] = aux[i-l];
			j++;
		}
		else if(aux[i - l] < aux[j-l])
		{
			arr[k] = aux[i-l];
			i++;
		}
		else
		{
			arr[k] = aux[j-l];
			j++;
		}
	}
}

但是这个实现有一些问题，比如我们没有保证i+size-1和i+size+size-1是否在数组边界内，另外，如果我们最后一段不足size长度怎么办，所以我们将代码作出如下改进

tmplate <typename T>
void mergeSortBU(T arr[],int n)
{
	int size,i;
	for(size = 1, size <= n; size+=size ) 
	{
		for(i = 0 ; i+size < n ; i += size + size ) 
		//这里改为i+size < n确保了后一段的存在，也保证了下标值不会越界
			__merge(arr, i, i+size-1,min( i+size+size-1,n-1));
			//这里与n-1取最小值可以保证我们最后一个下标不会越界
	}
}

然后我们和普通的自顶向下实现方法来进行一个比较，在对10000个随机生成的数字排序时，时间分别为：

可以看到自低向上还是快一点点的。

然后我们来对算法进行改进：

????1.在进行归并之前，先判断当数组是否已经有序，如果有序就不用进行归并处理

template <typename T>

void mergeSortBU(T arr[],int n)
{
	for(int sz = 1;sz <= n;sz += sz)
	{
		for(int i = 0;i + sz < n;i += sz+sz)
		{
			if(arr[i+sz-1] > arr[i+sz]) 
			//只有此时前一个小段最后一个数大于后一个小段第一个数字时才需要排序
				__merge(arr,i,i+sz-1, min(i+sz+sz-1,n-1));
		}
	}
}

我们这次用几乎有序的10000个数字来进行测试

第一个测试是优化后所需的时间（0.000577s），而第二个是没有优化所需的时间（0.001177s），相差了将近10倍，还是很可观的

????2.当划分的小段很小的时候我们采用插入排序的方法来代替归并排序

template <typename T>

void mergeSortBU(T arr[],int n)
{
	for(int sz = 1;sz <= n;sz += sz)
	{
		for(int i = 0;i + sz < n;i += sz+sz)
		{
			
			if(arr[i+sz-1] > arr[i+sz])
			{
			    if(i+sz+sz-1 <= 7) //若要合并的两小段长度合小于8的话，则用插入排序
				{
					inserectsort(arr,i,i+sz+sz-1);
				}
			    else
					__merge(arr,i,i+sz-1, min(i+sz+sz-1,n-1));
			}
		}
	}
}

可以看到性能还是有很大幅度提升的

需要注意的问题????

·我们在这种算法中没有使用数组的一个重要的性质：直接通过索引来获取元素

正是因为如此，我们可以用自底向上的方法，使用O（nlogn）的方法来完成对链表的排序，并且链表的归并排序不需要额外的空间

这篇文章里用递归的方法实现对链表用归并排序https://www.cnblogs.com/qiaozhoulin/p/4585401.html
我发现利用辅助数组也可以实现对链表的自顶向下排序，如果不使用辅助数组的话，可以实现对链表的自低向上排序。

emmm，介于我现在编程语言能力太薄弱，等我再练习一段时间后来将代码补全。