归并排序 递归版和非递归版的实现（java）

1. “分解”——将序列每次折半划分。
2. “合并”——将划分后的序列段两两合并后排序。

// 递归退出条件，及left》=right的时候 if (left < right) {    // 找出中间索引    center = (left + right) / 2;    // 对左边数组进行递归     mSort(k, 0, center);    // 对右边数组进行递归    mSort(k, center + 1, right);     // 合并   merging(k, left, center, right); }

 private static void merging(int[] k, int left, int center, int right) {        int tempArr[] = new int[k.length];// 存放数据的数组        // third记录中间数组的索引        int mid = center + 1;        int third = left;        int temp = left;        while (left <= center && mid <= right) {            // 从左右两个数组找出最小的数存入tempArr数组            if (k[left] < k[mid]) {                tempArr[third++] = k[left++];            } else {                tempArr[third++] = k[mid++];            }        }        // 剩余部分依次放入中间数组        while (mid <= right) {            tempArr[third++] = k[mid++];        }        while (left <= center) {            tempArr[third++] = k[left++];        }        // 将中间数组中的内容复制回原数组        while (temp <= right) {            k[temp] = tempArr[temp++];        }    }}

//下面是递归版的package com.xujun.mergesort;public class MergeSort {    static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5 };    public static void main(String[] args) {        System.out.println("before sort");        ArrayUtils.printArray(a);        mergeSort(a);        System.out.println("after sort");        ArrayUtils.printArray(a);    }    private static void mergeSort(int[] k) {        mSort(k, 0, k.length - 1);    }    private static void mSort(int[] k, int left, int right) {        int center        // 递归退出条件，及left》=right的时候        if (left < right) {            // 找出中间索引            center = (left + right) / 2;            // 对左边数组进行递归            mSort(k, 0, center);            // 对右边数组进行递归            mSort(k, center + 1, right);            // 合并            merging(k, left, center, right);        }    }    private static void merging(int[] k, int left, int center, int right) {       // 存放数据的数组        int tempArr[] = new int[k.length];        // third记录中间数组的索引        int mid = center + 1;        int third = left;        int temp = left;        while (left <= center && mid <= right) {            // 从左右两个数组找出最小的数存入tempArr数组            if (k[left] < k[mid]) {                tempArr[third++] = k[left++];            } else {                tempArr[third++] = k[mid++];            }        }        // 剩余部分依次放入中间数组        while (mid <= right) {            tempArr[third++] = k[mid++];        }        while (left <= center) {            tempArr[third++] = k[left++];        }        // 将中间数组中的内容复制回原数组        while (temp <= right) {            k[temp] = tempArr[temp++];        }    }}

   // 程序边界的处理非常重要        while (len <= t.length) {            for (int i = 0; i + len <= t.length - 1; i += len * 2) {        //    System.out.println("len="+len);                low = i;                mid = i + len - 1;                high = i + len * 2 - 1;                if (high > t.length - 1)                    high = t.length - 1;                merge(t, i, mid, high);            }//长度加倍            len += len;        }        return true;    }

package com.xujun.mergesort1;public class MergeSort2 {    /**     * 二路归并排序的递归算法-入口     *      * @param <T>     * @param t     * @return     */    public static <T extends Comparable> boolean mergeSortRecursive(T[] t) {        if (t == null || t.length <= 1)            return true;        MSortRecursive(t, 0, t.length - 1);        return true;    }    /**     * 二路归并排序的递归算法-递归主体     *      * @param <T>     * @param t     * @param low     * @param high     * @return     */    private static <T extends Comparable> boolean MSortRecursive(T[] t,            int low, int high) {        if (t == null || t.length <= 1 || low == high)            return true;        int mid = (low + high) / 2;        MSortRecursive(t, low, mid);        MSortRecursive(t, mid + 1, high);        merge(t, low, mid, high);        return true;    }    public static <T extends Comparable> boolean mergeSortNonRecursive(T[] t) {        if (t == null || t.length <= 1)            return true;        int len = 1;        int low = 0;        int mid;        int high;        // 程序边界的处理非常重要        while (len <= t.length) {            for (int i = 0; i + len <= t.length - 1; i += len * 2) {        //    System.out.println("len="+len);                low = i;                mid = i + len - 1;                high = i + len * 2 - 1;                if (high > t.length - 1)                    high = t.length - 1;                merge(t, i, mid, high);            }//长度加倍            len += len;        }        return true;    }    /**     * 将两个归并段合并成一个归并段     *      * @param <T>     * @param t     * @param low     * @param mid     * @param high     * @return     */    private static <T extends Comparable> boolean merge(T[] t, int low,            int mid, int high) {        T[] s = t.clone();// 先复制一个辅助数组        int i, j, k;// 三个指示器，i指示t[low...mid]，j指示t[mid+1...high]，k指示s[low...high]        for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {            if (t[i].compareTo(t[j]) <= 0) {                s[k] = t[i++];            } else {                s[k] = t[j++];            }        }        // 将剩下的元素复制到s中        if (i <= mid) {            for (; k <= high; k++) {                s[k] = t[i++];            }        } else {            for (; k <= high; k++) {                s[k] = s[j++];            }        }        for (int m = low; m <= high; m++) {// 将辅助数组中的排序好的元素复制回原数组            t[m] = s[m];        }        return true;    }    public static void main(String[] args) {        Integer[] arr = new Integer[] { 2, 3, 6, 8, 9, 2, 0, 1 };        long startTime = System.currentTimeMillis(); // 获取开始时间        mergeSortRecursive(arr);        long endTime = System.currentTimeMillis(); // 获取开始时间        System.out.println("执行时间：" + (endTime - startTime));        for (int i : arr) {            System.out.println(i);        }        startTime = System.currentTimeMillis(); // 获取开始时间        mergeSortNonRecursive(arr);        endTime = System.currentTimeMillis(); // 获取开始时间        System.out.println("执行时间：" + (endTime - startTime));        for (int i : arr) {            System.out.println(i);        }    }}