数据结构-归并排序

Love The Way You Lie 2021-11-19 14:06 330阅读 0赞

归并排序的基本思想：首先，将R\[0..n-1\]看成是n个长度为1的有序表，将相邻的有序表进行归并，得到n/2个长度为2的有序表；然后，再将这些有序表成对归并，得到n/4个长度为4的有序表，如此循环下去，最后得到一个长度为n的有序表。

注意的是：Merge()实现了一次归并，接下来需要利用MergePass()解决一趟归并问题。在某趟归并中，设各子表长度为length(最后一个字表的长度可能小于length)，则归并前R\[0..n-1\]中共有\[n/length\]个有序的字子表：R\[0..length-1\],R\[length..2length-1\],...,R\[(n/length)\*length..n-1\]。调用Merge()将相邻的一对子表进行归并时，必须对表的个数可能是奇数、以及最后一个子表的长度小于length这两种特殊情况进行特殊处理：若子表个数为奇数，则最后一个子表无须和其他子表进行归并；若子表个数为偶数，则要注意到最后一对子表中后一个子表的区间上界是n-1.

#include <iostream>
    
    using namespace std;
    
    void Merge(int* a,int low,int mid,int high){
        int* a1 = new int[high-low+1];
        int k = 0;          //k为a1的下标
        int i = low,j = mid+1;
        while(i <= mid && j <= high){   //两个小数组扫描
            if(a[i] <= a[j]){
                a1[k] = a[i];
                k++;
                i++;
            }
            else{
                a1[k] = a[j];
                k++;
                j++;
            }
        }
    
        while(i <= mid){
            a1[k] = a[i];
            i++;
            k++;
        }
    
        while(j <= high){
            a1[k] = a[j];
            j++;
            k++;
        }
    
        for(int i=low,k=0;i<=high;i++,k++){  //一节一节拷贝回原数组
            a[i] = a1[k];
        }
    
        delete[] a1;
    }
    
    void MergePass(int* a,int ChildLength,int n){
        int i;
        for(i=0;i+2*ChildLength-1<n;i=i+2*ChildLength){ //归并ChildLength长的两相邻子表
            Merge(a,i,i+ChildLength-1,i+2*ChildLength-1);
        }
        if(i+ChildLength-1 < n){    //余下两个子表，后者长度小于ChildLength
            Merge(a,i,i+ChildLength-1,n-1);
        }
    }
    
    void MergeSort(int* a,int n){
        for(int i=1;i<n;i*=2){
            MergePass(a,i,n);
        }
    }
    
    int main(){
        int a[] = {
        5,1,2,4,8,7,6,9,3,0,7,6};
        int n = sizeof(a)/sizeof(*a);
    
        MergeSort(a,n);
    
        for(int i=0;i<n;i++){
            cout << a[i] << " ";
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/wn19910213/p/3713791.html