package practice;

import edu.princeton.cs.algs4.*;

/*

 * 归并排序

 * 时间复杂度O(NlgN) N为数组长度

 * 归并排序在小数组上表现并不好可以用插入排序代替

 */

public class TestMain {

    public static void main(String[] args) {

        int[] a = new int[20];

        for (int i = 0; i < a.length; i++) {

            int temp = (int)(StdRandom.random()*100);

            a[i] = temp;

        }

        Merge.sort2(a);

        for (int i : a) {

            System.out.print(i+" ");

        }

    }

}

class Merge{

    private static int []anx; //辅助数组

    /*

     * 自底向上的归并排序(循序渐进)

     * 将数字两两分为一组，一直向上归并

     * 以下数字表示数组长度，假如要排一个长度为22的数组

     *  2   2   2   2   2   2   2   2   2   2   2

     *    4       4       4       4       4    2

     *        8               8             6

     *                16              6

     *                        22

     */

    public static void sort2(int[] a) {

        anx = new int[a.length];

        for (int sz = 1; sz < a.length; sz += sz) { //将要归并的大小(2*sz)翻倍

            for (int lo = 0; lo < a.length - sz; lo += (sz + sz)) { //将数组分为(2*sz)大小的子数组，分别归并

                merge(a, lo, lo + sz -1, Math.min(lo + 2*sz -1, a.length - 1));

            }

        }

    }

    /*

     * 自顶向下的归并排序(化整为零)

     * 将原数组循环一分为二，直到数组长度为2，再将小数组两两循环归并为原数组

     * 以下数字表示数组长度，当被分数字为单数时，前面的数组长度多一

     *                                 22

     *                       11                     11

     *                  6          5           6            5

     *               3     3    2     3     3      3     2      3

     *             2  1   2  1      2  1  2  1    2  1         2  1

     */

    public static void sort1(int[] a) {

        anx = new int[a.length];

        sort1(a, 0, a.length - 1);

    }

    private static void sort1(int []a, int lo, int hi) {

        if (lo >= hi) {

            return;

        }

        int mid = lo + (hi - lo)/2; //当被分数字为单数时，前面的数组长度多一

        sort1(a, lo, mid); //一分为二归并

        sort1(a, mid + 1, hi);

        merge(a, lo, mid, hi);

    }

    /*

     * 原地归并

     */

    public static void merge(int[] a, int lo, int mid, int hi) {

        int m = lo;

        int n = mid + 1; //当被分数字为单数时，将最中间的数字归到前面的数组(与上面对应)

        int []anx = new int[hi+1];

        for (int k = lo; k <= hi; k++) {

            anx[k] = a[k]; //将原数组复制到辅助数组

        }

        //mid将数组分为A，B两部分

        for (int k = lo; k <= hi; k++) {

            if (m > mid) { //A中取完，将B数组剩余部分存入a[]

                a[k] = anx[n++];

            }

            else if (n > hi) { //B中取完，将A数组剩余部分存入a[]

                a[k] = anx[m++];

            }

            else if (anx[n] < anx[m]) { //A，B中分别取出第一个，比较，并将小数装入a[]

                a[k] = anx[n++];

            }

            else {

                a[k] = anx[m++];

            }

        }

    }

}