归并排序的迭代(非递归)实现

发布于 2020-02-20  113 次阅读


本文主要介绍2路归并排序的递归实现。

2路归并排序的简单介绍

归并排序的算法思想

归并排序的算法思想基于对一个数组的两个已排序子数组的排序–Merge。归并排序先将数组进行分割,直到每个子数组只有一个元素,这样就可以将相邻的两个子数组看成是两个已排序的数组,构成Merge算法的先决条件,就可以用Merge算法进行排序,构成一个长度翻倍的子数组。对整个数组进行一次小长度的Merge算法后,可以构成一个长度翻倍的Merge算法的条件而进行Merge算法,最终对整个数组实现排序。

归并排序的流程图

下面是归并排序的流程图。

4237685-8247e09383de10a4.png

可以看到,每次程序都将数字两两分组(n/2个组),组内单独排序,最后将这些组两两合并,生成n/4个组,组内再单独排序。直到最后只剩下一个组为止。

2路归并排序的时间复杂度为O(logN)。

2路归并排序的迭代分布实现

基础–Merge

(一)Merge算法的前提:一个数组可以划分为两个已排序的子数组,如1 4 7 8 2 5 10,此数组可以划分为两个已排序的子数组:1 4 7 8和2 5 10。

(二)Merge算法的思想:

1、定义一个临时数组,长度为两个子数组的长度之和。int[] B = new int[high - low]

2、从两个子数组的头部开始进行比较,将较小的元素放入临时数组

int s = 0,t = 0,i = 0;
int l1 = mid - low;//第一部分的长度
int l2 = high - mid;//第二部分的长度
//从两个数组的头开始比较,将较小值填入临时数组
while(s < l1 && t < l2){
    if(A[low + s] >= A[mid + t]){
        B[i] = A[mid + t];
        t ++;
    }
    else{
        B[i] = A[low + s];
        s ++;
    }
    i ++;
}

直到某一个数组全部放入临时数组,然后将另一个数组的剩余部分放入临时数组,构成一个长度与原数组相同,且已排序的数组

//某一数组全部填入临时数组之后,将另一个数组的余下部分填入临时数组
if(s != l1){
    for(;s < l1;s++){
        B[i] = A[low + s];
        i++;
    }
}
else{
    for(;t < l2;t++){
        B[i] = A[mid + t];
        i++;
    }
}

因两个子数组是已排序的,所以各选一个进行比较之后就可确定更小元素在排好序的数组中的位置,而无需考虑其他的问题。

分割数组

归并排序的第一步是对数组进行分割,只有分割到满足Merge算法的前提,才能使算法正确运行。

为了构成Merge算法的前提,所以必须分割到最小限度。

我用一个step来表示分割后的子数组长度,step是一个2的整数次幂,如:step:1->2->4->8->..

当step为1的子数组排序完之后,就自然构成了多个满足Merge算法前提的step为2的子数组,如此迭代即可完成算法。

//因归并排序的第一步是划分,步长一步步翻倍
//因待排序的数组的长度可能是奇数,而步长总是2的整数倍,故将step的上限定为数组长度的一半并向上取整,即c.length/2 + 1
while(step <= c.length/2 + 1){
    //以步长为基础,对原数组进行切分,分别排序
    for(int i = 0;i < c.length;i = i + step *2){
        //因数组长度可能为奇数,故可能最后存在不满步长的分割情况,需要单独判断
        if((i + step * 2) > c.length){
            merge(c,i,i+step,c.length);
            continue;       
        }
        //若不是上述情况,则正常分割
        merge(c,i,i+step,i+step * 2);
    }
    step = step * 2;//步长翻倍增长
}

此处有一个非常关键的问题,就是step的界限控制,及传递给Merge算法的参数控制问题。

(一)step的界限控制

step是用来控制分割的关键参数,因原数组的长度可能为奇数,而step总是2的整数次幂,所以若不进行区别控制,将会导致最后结果为一个可以分割成两个已排序的子数组的新数组,而没有进行最后的一步归并排序,原因就在于step的界限控制。

这里我将step的界限控制在step <= c.length/2 + 1即step的上限定为数组长度的一半并向上取整,这样即使存在奇数的原数组长度,也可进行完全的归并排序。

例子:

1、原数组:5 2 4,数组长度为3,是奇数,且3/2 + 1 = 2,即须排序2次。

验证:第一次排序:step = 1,5 2 =>2 5=>2 5 4;第二次排序:step = 2,2 5 4=>2 4 5,排序2次,结果正确。

若不向上取整,则3/2 = 1,只排序1次,所以结果必然是错误的。

2、原数组:5 2 4 6,数组长度为4,是偶数,且4/2+1 = 3,而step为2的整数次幂,所以排序次数为2次。

验证:第一次排序:step = 1,5 2 4 6 =>2 5 4 6;第二次排序:step = 2,2 5 4 6=>2 4 5 6,排序2次,结果正确。

在对所有元素进行一次归并后,需要将step翻倍,即step = step * 2

(二)传递给Merge算法的参数控制

1、参数解释

Merge算法的参数可以根据需求设置,此处我设置为4个参数merge(int[] A,int low,int mid,int high),A为原数组,low为在数组A中须排序的部分的最小位置,mid为两个已排序的子数组的分割,high为在数组A中须排序的部分的最大位置。如2 5 4 6,在次数组中,low为0,mid为2,high为4。所以明显的,第一个子数组的长度为mid-low = 2,第二个子数组的长度为high-mid = 2,结果正确。

2、参数控制

因为原数组的长度可能为奇数,而step为2的幂,所以会存在第一次排序时,最后一个子数组没有归并对象,在之后的排序中,两边数组的长度不等的情况,若不加区别控制,则会造成数组越界的问题。

例子:

原数组:2 5 4

过程:

一次merge:step=1,第一部分2 5构成可用merge(c,i,i+step,i+step 2)进行排序的数组,即merge(c,0,1,2),结果正确且未数组越界;第二部分4,没有归并对象,若用merge(c,i,i+step,i+step 2)即merge(c,2,3,4),明显数组越界。

所以需做如下控制:

if((i + step * 2) > c.length){
    merge(c,i,i+step,c.length);
    continue;
}
//若不是上述情况,则正常分割
merge(c,i,i+step,i+step * 2);

在此处,我加上了区别控制。

当发现i + step 2,即参数high超过了原数组的长度,则表明最后一个子数组不能满足两个子数组长度相等的情况,故不能用普遍的参数merge(c,i,i+step,i+step 2)来处理,而需要将最后一个参数改为c.length,确保在后续操作时,不出现数组越界的情况。

Merge算法并不需要两个子数组的长度相等,所以这样不会造成算法的失败。

具体算法

附上我写的归并排序算法

public class BottomUpSort {
    int[] c;

    void merge(int[] A,int low,int mid,int high){
        //对一个数组的两部分已排序的部分进行排序
        int s = 0,t = 0,i = 0;
        int[] B = new int[high - low];//定义一个新数组
        int l1 = mid - low;//第一部分的长度
        int l2 = high - mid;//第二部分的长度
        //从两个数组的头开始比较,将较小值填入临时数组
        while(s < l1 && t < l2){
            if(A[low + s] >= A[mid + t]){
                B[i] = A[mid + t];
                t ++;
            }
            else{
                B[i] = A[low + s];
                s ++;
            }
            i ++;
        }
        //某一数组全部填入临时数组之后,将另一个数组的余下部分填入临时数组
        if(s != l1){
            for(;s < l1;s++){
                B[i] = A[low + s];
                i++;
            }
        }
        else{
            for(;t < l2;t++){
                B[i] = A[mid + t];
                i++;
            }
        }
        //将原数组被排序部分用临时数组替换
        for(i = 0;i < high - low;i++){
            A[low + i] = B[i];
        }
    }

    void combine(int step){
        //因归并排序的第一步是划分,步长一步步翻倍
        //因待排序的数组的长度可能是奇数,而步长总是2的整数倍,故将step的上限定为数组长度的一半并向上取整,即c.length/2 + 1
        while(step <= c.length/2 + 1){
            //以步长为基础,对原数组进行切分,分别排序
            for(int i = 0;i < c.length;i = i + step *2){
                //因数组长度可能为奇数,故可能最后存在不满步长的分割情况,需要单独判断
                if((i + step * 2) > c.length){
                    merge(c,i,i+step,c.length);
                    continue;
                }
                //若不是上述情况,则正常分割
                merge(c,i,i+step,i+step * 2);
            }
            step = step * 2;//步长翻倍增长
        }
    }

    public static void main(String[] args){
        //初始化类及原数组
        BottomUpSort b = new BottomUpSort();
        b.c = new int[]{42,661,32,7,62,38,3};
        System.out.print("data: ");
        for(int i = 0;i < b.c.length;i++){
            System.out.print(b.c[i] + " ");
        }
        //进行归并排序
        b.combine(1);
        System.out.print("\nafter sort,result: ");
        for(int i = 0;i < b.c.length;i++){
            System.out.print(b.c[i] + " ");
        }
    }
}

算法笔记的迭代归并排序代码

归并排序每次分组时组内元素上限都是2的幂次。

于是得到以下思路:

令步长初值为2,然后将数组中每step个元素作为一组,将其内部排序(把左边step/2个元素于右边step/2个元素合并,而若元素个数不超过step/2则不操作不排序)

再令step*2,重复上面操作,直到step/2超过元素个数n。

问题:

(1)再令step*2,重复上面操作,直到step/2超过元素个数n。为什么这里是step/2?

#include <stdio.h>
#include <stdlib.h>
int n; // 组数
void mergeSort( int A[] )
{
    for(int step = 2; step / 2 <= n; step *= 2){
        for(int i = 1; i <= n; i += step){//对每一组进行for循环
            int mid = i + step / 2 - 1;
            if(mid + 1 <= n){
                merge(A, i, mid, mid+1, min(i + strp -1,n));
            }
        }
    }
}
void merge(int a[], int l1, int r1, int l2, int r2){
    int i = l1, j = l2;
    int temp[maxn], index = 0;  //temp临时存放合并后的数组,index为其下标
    while(i <= r1 && j <= r2){ //保证两个数组不出界到对面捣乱
        if(a[i] <= a[j]) //判断数组1的第i个元素(left)是否<=数组2的第j个元素(mid+1)(i=j)
            temp[index++] = a[i++];
        else //哪个数组的相应元素更小就先加入,并统计归并后的数组元素个数(index)
            temp[index++] = a[j++];
    }
    while(i <= r1) temp[index++] = a[i++]; //将[l1,r1]的剩余元素加入序列temp
    while(j <= r2) temp[index++] = a[j++]; //将[l2,r2]的剩余元素加入序列temp
    for(i = 0; i < index; i++){
        a[l1 + i] = temp[i]; //
    }
}
int main(){

    while(scanf("%d", &n) != EOF, n--){
        long long m; // 待排序数字的个数
        scanf("%lld", &m);
        int a[maxn];
        for(int i = 0; i < m; i++){
            scanf("%d", &a[i]);
        }
        mergeSort(a, 0, m - 1);
        for(int i = 0; i < m; i++){
            printf("%d\n", a[i]);
        }
    }
}

拓展:
如果下标为0开始,代码应该做何修改?
(挖坑,待解决)

分析时间复杂度

方便起见, 这里使用 2^N 个数据为例, 首先我们定义一个变量 N 代表 常量 C 代表分解步骤与处理每个数组元素需要的时间的和(这里可能不是非常准确,但是不妨碍我们求解归并排序算法的最差运行时间, 只是多算了一些分解数组的时间)

下图图示了归并排序的归并树, 每一层的代价为 CN 一共有log2(N+1), 所有的代价和为 T(N) = C(log(N)) + C(N), 使用大 O 记号去掉常量和低阶项得到该算法时间复杂度O(Nlog(N))

参考

九大排序之归并排序--实现及注意点

算法笔记3105ProblemB 基础排序III:归并排序

本文标题:《归并排序的迭代(非递归)实现》

本文链接:https://wnag.com.cn/900.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。