归并排序（递归和非递归）

水深无声 2022-05-28 01:44 198阅读 0赞

学习之后，自己练习手写一下排序算法，加深印象

**原理：假设初始序列含有n个记录，则可以看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的子序列；再两两归并，如此重复，最终得到一个长度为n的有序序列**

**递归方法**

#define MAXSIZE 10
    #include <stdio.h>
    struct a{
        int array[MAXSIZE];    //数组用于存储排序数据 
        int length;           //用于存储数组长度信息， 
    };
    
    void init_array(struct a *L){   //初始化数组 
        int i;
        L->length = MAXSIZE-1;
        for (i=1;i<=L->length;i++){     //索引为0的项留作备用 
            scanf("%d",&(L->array[i]));
        }
    }
    
    void swap(struct a *L,int i,int j){   //交换数组项 
        int temp = L->array[i];
        L->array[i] = L->array[j];
        L->array[j] = temp;
    }
    
    void print(struct a *L){    //打印数组项 
        int i;
        for (i=1;i<=L->length;i++){
            printf("%d ",L->array[i]);
        }
    }
    
    void Merge(struct a *L, int first, int middle, int last){   //将L->array中的两个子序列合并 
        int Index1 = first, Index2 = middle+1, mergeIndex = first;   //Index1和Index2分别为两个子序列的索引，mergeIndex为合并后序列的索引 
        int temp[L->length+1];    //创建临时序列，用作存储合并后的值 
        int i;
    
        for(; Index1<=middle && Index2 <=last; mergeIndex++){   //依次对比两个子序列的值，并将较小的值填入临时序列中，当一个子序列没有值可以比较时，终止 
            if (L->array[Index1] < L->array[Index2]){
                temp[mergeIndex] = L->array[Index1++];
            }else{
                temp[mergeIndex] = L->array[Index2++];
            }
        }
    
        if (Index1 <= middle){      //将剩下的第一个子序列填入到临时序列 
            for (; Index1 <= middle; Index1++){
                temp[mergeIndex++] = L->array[Index1];
            }
        }
    
        if (Index2 <= last){    //将剩下的第二个子序列填入到临时序列 
            for (; Index2 <= last; Index2++){
                temp[mergeIndex++] = L->array[Index2];
            }
        }
    
        for (i=first; i<mergeIndex; i++){  //将临时序列的值复制给L->array 
            L->array[i] = temp[i];
        }
    
    }
    
    void MSort(struct a*L, int first, int last){   //first和last分别为序列第一项和最后一项的索引
        int middle;                
        if (first < last){    //当first和last相等时，即子序列只有一个数时，不必再继续划分子序列了 
            middle = first + (last-first)/2;  //作为中点坐标，平分整个序列 
            MSort(L,first,middle);      // 归并索引从first到middle的子序列 
            MSort(L,middle+1,last);     //归并索引从middle+1到last的子序列 
            Merge(L,first,middle,last);  //将两个子序列合并 
        }
    }
    
    void MergeSort(struct a *L){   //排序算法 
        MSort(L,1,L->length);
    } 
    
    int main(){
        struct a List;
        init_array(&List);
        printf("排序前:");
        print(&List);
        MergeSort(&List);
        printf("\n排序后:");
        print(&List);
        return 0;
    }

![这里写图片描述][70]  
两个子序列的合并过程如上图所示，首先比较10和20这两个数，10比较小，则将其填入临时序列的第一项，再比较30和20这两个数，20比较小，则将20填入临时序列的第二项，如此比较下去，直到一个子序列到头，此时将另一个子序列剩下的，没有比较的值依次填入临时序列，最终得到合并完成的临时序列，再将其赋值给原始序列即可。  
![这里写图片描述][70 1]

**非递归算法**

#define MAXSIZE 10
    #include <stdio.h>
    struct a{
        int array[MAXSIZE];    //数组用于存储排序数据 
        int length;           //用于存储数组长度信息， 
    };
    
    void init_array(struct a *L){   //初始化数组 
        int i;
        L->length = MAXSIZE-1;
        for (i=1;i<=L->length;i++){     //索引为0的项留作备用 
            scanf("%d",&(L->array[i]));
        }
    }
    
    void swap(struct a *L,int i,int j){   //交换数组项 
        int temp = L->array[i];
        L->array[i] = L->array[j];
        L->array[j] = temp;
    }
    
    void print(struct a *L){    //打印数组项 
        int i;
        for (i=1;i<=L->length;i++){
            printf("%d ",L->array[i]);
        }
    }
    
    void Merge(struct a *L, int first, int middle, int last){   //将L->array中的两个子序列合并 
        int Index1 = first, Index2 = middle+1, mergeIndex = first;   //Index1和Index2分别为两个子序列的索引，mergeIndex为合并后序列的索引 
        int temp[L->length+1];    //创建临时序列，用作存储合并后的值 
        int i;
    
        for(; Index1<=middle && Index2 <=last; mergeIndex++){   //依次对比两个子序列的值，并将较小的值填入临时序列中，当一个子序列没有值可以比较时，终止 
            if (L->array[Index1] < L->array[Index2]){
                temp[mergeIndex] = L->array[Index1++];
            }else{
                temp[mergeIndex] = L->array[Index2++];
            }
        }
    
        if (Index1 <= middle){      //将剩下的第一个子序列填入到临时序列 
            for (; Index1 <= middle; Index1++){
                temp[mergeIndex++] = L->array[Index1];
            }
        }
    
        if (Index2 <= last){    //将剩下的第二个子序列填入到临时序列 
            for (; Index2 <= last; Index2++){
                temp[mergeIndex++] = L->array[Index2];
            }
        }
    
        for (i=first; i<mergeIndex; i++){  //将临时序列的值复制给L->array 
            L->array[i] = temp[i];
        }
    
    }
    
    
    void MergeSort(struct a *L){   //排序算法 
        int step;             //每个子序列的长度
        int i;
        for (step=1; step<L->length; step*=2){  //子序列的长度随着归并的进行，以2为倍速增大 
            for (i=1; i<=L->length/(2*step); i++){   //i为将整个序列划分为包含两个子序列的组数 
                Merge(L,(i-1)*step*2+1,i*step*2-step,i*step*2);   //将两两子序列进行合并 
            }
            if (L->length/(2*step) == 0){    //当不足以再划分子序列时
                Merge(L,1,step,L->length);   //合并最后两个子序列 
            }
        }
    
    } 
    
    int main(){
        struct a List;
        init_array(&List);
        printf("排序前:");
        print(&List);
        MergeSort(&List);
        printf("\n排序后:");
        print(&List);
        return 0;
    }

非递归归并排序做法直接了当，从最小的序列开始归并直至完成。不需要像递归归并算法那样，需要先拆分递归，再归并退出递归，节省了时间和空间  
![这里写图片描述][70 2]

**算法时间复杂度：O(nlogn)**

[70]: /images/20220528/0a3ac90fb85044fbaac70c03586d5e87.png
[70 1]: /images/20220528/e05a6e997d854f6cbfed8b4a105d663d.png
[70 2]: /images/20220528/19cf971460384160bdbfcbc0324845f4.png