常见排序算法(6)--归并排序(非递归版)

非递归归并排序算法

非递归排序与递归排序相反，将一个元素与相邻元素构成有序数组，再与旁边数组构成有序数组，直至整个数组有序。

代码实现

// 归并排序非递归版
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刚好是2ⁿ，如2，4，8，16这样的，那么最后的k就等于 length/2 。如果length不是2ⁿ这样的数，那么最后的k就等于2ⁿ，其中n=log(length)的整数部分；如length=34，n=5，k就等于32。k其实就是小于length的最大的2ⁿ的数。所以这里的边界条件写k < length是对的。

其实非递归归并排序算法的代码也不多，但是比较难理解，不过我觉得我前面的解释的很清楚了，如果暂时看不懂，多读几遍。还是不懂的话可以在评论中@我。