非递归归并排序算法
非递归排序与递归排序相反，将一个元素与相邻元素构成有序数组，再与旁边数组构成有序数组，直至整个数组有序。
代码实现
// 归并排序非递归版
void MergeSort2(int *arr,int length)
{
int k = 1;/*k用来表示每次k个元素归并*/
int *temp = (int *)malloc(sizeof(int) * length);
while(k < length)
{
MergePass(arr, k, length, temp);
k *= 2;
}
free(temp);
}
void MergePass(int *arr, int k, int n, int *temp)
{
int i = 0;
//从前往后,将2个长度为k的子序列合并为1个
while(i < n - 2*k + 1)
{
merge(arr, i, i + k-1, i + 2*k - 1, temp);
i += 2*k;
}
//合并有序的左半部分以及不及一个步长的右半部分
if(i < n - k )
{
merge(arr, i, i+k-1, n-1, temp);
}
}
直接说代码吧。MergeSort2函数就是归并排序的非递归方法，里面就是个while循环，单看MergeSort2方法可能不太明白，我们要先明白核心方法MergePass做了什么。
while循环的解释
MergePass里面的while循环，其实就是把将2个长度为k的子序列合并为1个(其中merge方法跟上篇文章的递归版归并排序的merge是完全一样的)。最开始我看到这个方法的时候也看不懂，啥i < n - 2*k + 1，为啥又是i, i + k-1, i + 2*k - 1这3个数。其实它是把arr数组分为了这样的小序列。如下标为[i,i+k-1],这是左子序列，刚好有k个元素，右子序列为[i+k,i+2k-1]，也是k个。如果数组的元素个数n刚好是2k的倍数那是最好的，各个长度为k的左右子序列分别合并，没有遗留下不能配对的元素。但是一般不会这么凑巧，一般n都不会是2k的倍数，所以i < n - 2*k + 1等价于i + 2k -1 < n等价于i + 2k -1 <= n-1，其中i + 2k -1刚好是右子序列的右边界，这个i + 2k -1 <= n-1保证了把数组中的可以配对的子序列全都剥离出来了。举个例子，假设k=1，某数组有7个元素，前4个元素可以完全配对。
if判断的解释
如果n不是2k的倍数，那么所以余下的元素个数就是在1到2k-1个之间。下面的if就是解决这部分的。为什么有i < n - k这个判断条件？其实如果余下多余的元素，也不是一定要在这次的MergePass方法中处理。只有当余下的元素的个数多于k个时(也就是存在右半部分的子序列，1=<右半部分的个数<=k-1)需要把有k个元素的左序列与不足k个元素的右序列merge。假设余下的元素个数<=k个，那么在这次MergePass不用处理(会在最后一次MergePass中被merge)。左序列的右边界是i+k-1一定要小于最后一个元素的下标n-1，所以有i+k-1<n-1，所以有i < n - k这个条件。这个判断条件就保证了肯定存在右子序列。
MergeSort2方法的边界条件的解释
MergeSort2方法中有个while循环，它的边界条件是k < length。这里我们探究一下，可以写成k <= length吗？其实k的最大值是可以求出来的，现在我们就来算k的最大值。如果数组的个数的length刚好是2n，如2，4，8，16这样的，那么最后的k就等于 length/2 。如果length不是2n这样的数，那么最后的k就等于2n，其中n=log(length)的整数部分；如length=34，n=5，k就等于32。k其实就是小于length的最大的2n的数。所以这里的边界条件写k < length是对的。
其实非递归归并排序算法的代码也不多，但是比较难理解，不过我觉得我前面的解释的很清楚了，如果暂时看不懂，多读几遍。还是不懂的话可以在评论中@我。
网友评论