【排序算法】归并排序算法 Java实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

基本思想
1. 可以将一组数组分成A,B两组
2. 依次类推，当分出来的小组只有一个数据时，就可以认为这个小组已经达到了有序
3. 然后合并相邻的两个小组
4. 这样先通过递归的分解数组，再合并数组就可以完成 归并排序。
两个数组的合并算法实现

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++];

        }

    }

}

算法实现

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

巴特西

【排序算法】归并排序算法 Java实现

最新文章

热门文章