（基于Java）算法之合并排序

合并排序（MergeSort）：又叫歸并排序，該算法是用分治政策實作對N個元素進行排序的算法。時間複雜度為O(nlogn)。

合并排序的基本思想是：将待排序元素分成大小大緻相同的兩個子集合，分别對兩個子集合進行排序，最終将排好序的子集合合并成所要求的排好序的集合，如圖：

合并排序的方法可以用遞歸來實作，代碼如下：

private static int[] mergeSort(int[] num,int[] num1,int l,int r){
    int mid;
    int[] num2 = new int[r + 1];
    if(l == r)
        num1[l] = num[l];
    else{
        mid = (l + r) / 2;
        //左半部分遞歸
        mergeSort(num,num2,l,mid);
        //右半部分遞歸
        mergeSort(num,num2,mid+1,r);
        //由num2去歸并，傳回的值放到num1中,num1賦新值，其實就是更新num2,然後讓num2再去歸并，傳回新的num1
        merge(num2,num1,l,mid,r);
    }
    return num1;
}
           

合并步驟的代碼如下：

private static void merge(int[] num,int[] num1,int l,int mid,int r){
    int i,j,k;
    i = l;
    j = mid +1;
    k = l;
    //選擇較小的數放入num1數組中
    while(i <= mid && j <= r){
        if(num[i] <= num[j])
            num1[k++] = num[i++];
        else
            num1[k++] = num[j++];
    }
    //将剩下的數放入num1數組中
    while(i <= mid)                   
        num1[k++] = num[i++];
    while(j <= r)
        num1[k++] = num[j++];
}
           

測試代碼：

public static void main(String[] args) {
    int[] aw={73,12,87,43,25,93,32,26,57,65};
    int[] aw2 = new int[aw.length];
    aw = mergeSort(aw,aw2,0,aw.length-1);
    for(int i : aw)
        System.out.print(i+" ");
}
           

因為結果無異常，就不貼出輸出結果了，有興趣的讀者可以自己動手試試。

以上代碼的l和r都表示left和right，即要排序的左邊界和右邊界。

有不對之處以及改進建議，歡迎提出！