【排序算法】歸並排序算法 Java實現

歸並排序是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

1. 基本思想

   1. 可以將一組數組分成A,B兩組
   2. 依次類推，當分出來的小組只有一個數據時，就可以認為這個小組已經達到了有序
   3. 然後合並相鄰的兩個小組
   4. 這樣先通過遞歸的分解數組，再合並數組就可以完成 歸並排序。

2. 兩個數組的合並算法實現

public class Merge {

    public static void main(String[] args) {
        int[] arrayA = new int[] { 1, 6, 3, 4, 5 };
        int[] arrayB = new int[] { 2, 7, 8, 9 };
        int[] temp = new int[9];

        mergeArray(arrayA, arrayA.length, arrayB, arrayB.length, temp);

        for (int i : temp) {
            System.out.print(i + " ");
        }

    }

    /**
     * 將數組 arrayA[] 和 arrayB[] 合並到 arrayC[]
     */
    private static void mergeArray(int arrayA[], int lengthA, int arrayB[], int lengthB, int temp[]) {
        int i = 0, j = 0, k = 0;

        while (i < lengthA && j < lengthB) { // 將兩個有序的數組合並，排序到輔助數組temp中
            if (arrayA[i] > arrayB[j]) {
                temp[k++] = arrayB[j++];
            }
            else {
                temp[k++] = arrayA[i++];
            }
        }

        while (i < lengthA) {   // 如果arrayA[] 中還沒有合並完的，則直接將arrayA[]中沒有合並的數組復制到輔助數組中
            temp[k++] = arrayA[i++];
        }

        while (j < lengthB) { // 如果arrayB[] 中還沒有合並完的，則直接將arrayB[]中沒有合並的數組復制到輔助數組中
            temp[k++] = arrayB[j++];
        }
    }

}

1. 算法實現

public class MergeSorter {
    public void sort(int[] array) {
        int[] auxArray = new int[array.length];
        mergeSort(array, auxArray, 0, array.length - 1);
    }

    /**
     * 基於分治思想，執行歸並排序
     */
    private void mergeSort(int[] array, int[] auxArray, int low, int high) {
        int dividedIndex = 0;
        if (low < high) {
            dividedIndex = (low + high) / 2;
            mergeSort(array, auxArray, low, dividedIndex); // 左邊遞歸歸並排序
            mergeSort(array, auxArray, dividedIndex + 1, high); // 右邊遞歸歸並排序
            mergeArray(array, auxArray, low, dividedIndex, high); // 合並分治結果
        }
    }

    private void mergeArray(int[] array, int[] temp, int low, int dividedIndex, int high) {
        int i = low; // 指向左半分區的指針
        int j = dividedIndex + 1; // 指向右半分區的指針
        int k = 0; // 指向輔助數組的指針

        while (i <= dividedIndex && j <= high) {
            if (array[i] > array[j]) {
                temp[k++] = array[j++];
            } else {
                temp[k++] = array[i++];
            }
        }

        while (i <= dividedIndex) {
            temp[k++] = array[i++];
        }

        while (j <= high) {
            temp[k++] = array[j++];
        }

        // 最後把輔助數組的元素復制到原來的數組中去，歸並排序結束
        for (i = low, k = 0; i <= high; i++, k++) {
            array[i] = temp[k];
        }
    }
}

參考文章：
1.http://shiyanjun.cn/archives/820.html
2.http://blog.csdn.net/morewindows/article/details/6678165