歸并排序（遞歸和非遞歸）

學習之後，自己練習手寫一下排序算法，加深印象

原理：假設初始序列含有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-;
    for (i=;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=;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+, mergeIndex = first;   //Index1和Index2分别為兩個子序列的索引，mergeIndex為合并後序列的索引 
    int temp[L->length+];    //建立臨時序列，用作存儲合并後的值 
    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)/;  //作為中點坐标，平分整個序列 
        MSort(L,first,middle);      // 歸并索引從first到middle的子序列 
        MSort(L,middle+,last);     //歸并索引從middle+1到last的子序列 
        Merge(L,first,middle,last);  //将兩個子序列合并 
    }
}

void MergeSort(struct a *L){   //排序算法 
    MSort(L,,L->length);
} 

int main(){
    struct a List;
    init_array(&List);
    printf("排序前:");
    print(&List);
    MergeSort(&List);
    printf("\n排序後:");
    print(&List);
    return ;
}
           

兩個子序列的合并過程如上圖所示，首先比較10和20這兩個數，10比較小，則将其填入臨時序列的第一項，再比較30和20這兩個數，20比較小，則将20填入臨時序列的第二項，如此比較下去，直到一個子序列到頭，此時将另一個子序列剩下的，沒有比較的值依次填入臨時序列，最終得到合并完成的臨時序列，再将其指派給原始序列即可。

非遞歸算法

#define MAXSIZE 10
#include <stdio.h>
struct a{
    int array[MAXSIZE];    //數組用于存儲排序資料 
    int length;           //用于存儲數組長度資訊， 
};

void init_array(struct a *L){   //初始化數組 
    int i;
    L->length = MAXSIZE-;
    for (i=;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=;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+, mergeIndex = first;   //Index1和Index2分别為兩個子序列的索引，mergeIndex為合并後序列的索引 
    int temp[L->length+];    //建立臨時序列，用作存儲合并後的值 
    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=; step<L->length; step*=){  //子序列的長度随着歸并的進行，以2為倍速增大 
        for (i=; i<=L->length/(*step); i++){   //i為将整個序列劃分為包含兩個子序列的組數 
            Merge(L,(i-)*step*+,i*step*-step,i*step*);   //将兩兩子序列進行合并 
        }
        if (L->length/(*step) == ){    //當不足以再劃分子序列時
            Merge(L,,step,L->length);   //合并最後兩個子序列 
        }
    }

} 

int main(){
    struct a List;
    init_array(&List);
    printf("排序前:");
    print(&List);
    MergeSort(&List);
    printf("\n排序後:");
    print(&List);
    return ;
}
           

非遞歸歸并排序做法直接了當，從最小的序列開始歸并直至完成。不需要像遞歸歸并算法那樣，需要先拆分遞歸，再歸并退出遞歸，節省了時間和空間

算法時間複雜度：O(nlogn)