常见排序算法(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刚好是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是对的。

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,223评论 0 52
  • 总结一下常见的排序算法。 排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序...
    jiangliang阅读 1,391评论 0 1
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,286评论 0 2
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,417评论 0 2
  • 万丈红尘三杯酒, 千秋大业一壶茶。 大家好,我是洛苏。一个锦绣峨眉大山深入土生土长的女子,深爱古典文化,更爱...
    茶女落苏阅读 512评论 0 0