排序算法之歸并排序及Java實作

一、排序算法的分類

1. 選擇排序（直接選擇排序，堆排序）
2. 交換排序（冒泡排序，快速排序）
3. 插入排序（直接插入排序，希爾排序）
4. 歸并排序
5. 桶式排序
6. 基數排序

二、歸并排序的原理

歸并排序利用的是分治的思想實作的，對于給定的一組資料，利用遞歸與分治技術将資料序列劃分成為越來越小的子序列，之後對子序列排序，最後再用遞歸方法将排好序的子序列合并成為有序序列。合并兩個子序列時，需要申請兩個子序列加起來長度的記憶體，臨時存儲新的生成序列，再将新生成的序列指派到原數組相應的位置。

三、歸并排序的實作

public class MergeSort {

    public static void merSort(int[] arr,int left,int right){

        if(left<right){
            int mid = (left+right)/;
            merSort(arr,left,mid);//左邊歸并排序，使得左子序列有序
            merSort(arr,mid+,right);//右邊歸并排序，使得右子序列有序
            merge(arr,left,mid,right);//合并兩個子序列
        }
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + ];//ps：也可以從開始就申請一個與原數組大小相同的數組，因為重複new數組會頻繁申請記憶體
        int i = left;
        int j = mid+;
        int k = ;
        while(i<=mid&&j<=right){
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while(i<=mid){//将左邊剩餘元素填充進temp中
            temp[k++] = arr[i++];
        }
        while(j<=right){//将右序列剩餘元素填充進temp中
            temp[k++] = arr[j++];
        }
        //将temp中的元素全部拷貝到原數組中
        for (int k2 = ; k2 < temp.length; k2++) {
            arr[k2 + left] = temp[k2];
        }
    }
    public static void main(String args[]){
        int[] test = {,,,,,,,,};
        merSort(test,,test.length-);
        for(int i=; i<test.length;i++){
            System.out.print(test[i] + " ");
        }
    }

}
           

測試結果

2 3 5 6 7 9 10 11 12