归并排序

1. 递归实现

package pr.cgl.test;

/**
 * Created by LL on 2017/5/24.
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] a = {3, 23, 22, 1, 5, 3, 4, 44, 0};

        sort(a, 0, a.length - 1);
    }

    /**
     * 递归调用排序，当切分成只有一个元素时递归结束，即当start=end时
     * @param a
     * @param start
     * @param end
     */
    public static void sort(int[] a, int start, int end){
        int mid = (start + end) / 2;
        if(start < end){
            sort(a, start, mid);
            sort(a, mid + 1, end);
            merge(a, start, mid, end);
        }
    }

    /**
     *
     * @param a  上次排序完的数组
     * @param start
     * @param mid
     * @param end
     */
    public static void merge(int[] a, int start, int mid, int end) {
        int[] left = new int[mid - start + 1];
        int[] right = new int[end - mid];

        int i = 0, j = 0;
        for (i = start; i <= mid; i++) {
            left[i-start] = a[i];
        }

        for (j = mid + 1; j <= end; j++) {
            right[j - mid - 1] = a[j];
        }

        int flagL = 0, flagR = 0;

        i = start;
        while (flagL<left.length && flagR<right.length){
            if(left[flagL] < right[flagR]){
                a[i] = left[flagL];
                flagL ++;
            }else{
                a[i] = right[flagR];
                flagR ++;
            }
            i++;

        }
        while(flagL < left.length){
            a[i++] = left[flagL++];
        }
        while(flagR < right.length){
            a[i++] = right[flagR++];
        }

        print(a);
    }


    public static void print(int[] arr){
        System.out.println();
        for(int x: arr){
            System.out.print(x+" ");
        }
    }
}

2. 非递归实现

package pr.cgl.test;

/**
 * Created by LL on 2017/5/25.
 */
public class MergeSortNoRecursive {
    public static void main(String[] args) {
        int[] a = {3,23,22,1,5,3,4,44,0};
        int len = a.length;
        print(a);
        execute(a);

        int mid = (len-1)/2;
        merge(a, 0, mid, len - 1);
        print(a);
    }

    public static void execute(int[] a) {
        int len = a.length;
        int end = len - 1;
        int step = 2;
        while(step < len){
            int part = 0, s = 0, e = 0;
            int parts = len%step==0? len/step: len/step + 1;
            while(e <= end && part< parts){
                s = step * part;
                e = step * (part+1) - 1;
                e = e > end? end: e;
                int mid = (s + e) / 2;
                merge(a, s, mid, e);
                part ++;

            }
            step = step * 2;
        }

        if(len%2==1){
            step = step >> 1;
            merge(a, 0, step-1, end);
        }
    }

    public static void merge(int[] data, int start, int mid, int end) {

        if(start < end){
            int temp[]  = new int[data.length];

            int i = 0, flagL = start, flagR = mid + 1;
            for(i = 0; i <= data.length - 1; i ++){
                temp[i] = data[i];
            }

            i = start;
            while(flagL <= mid && flagR <= end){
                if(temp[flagL] < temp[flagR]){
                    data[i] = temp[flagL];
                    flagL ++;
                }else{
                    data[i] = temp[flagR];
                    flagR ++;
                }
                i++;
            }

            while(flagL <= mid){
                data[i++] = temp[flagL++];
            }

            while (flagR <= end){
                data[i++] = temp[flagR++];
            }
        }
    }

    public static void print(int[] arr){
        System.out.println();
        for(int x: arr){
            System.out.print(x+" ");
        }
    }
}