[TOC]

algorithm 4th(2.2)歸并排序

說明：

• 歸并排序需要一個和要排序數(shù)組一樣容量的的數(shù)組
• 歸并排序分為自頂向下和自下向上兩種方案崩泡，自下向上用于鏈表實(shí)現(xiàn)（只需調(diào)整指針即可）
• 歸并排序中，使用插入排序處理小規(guī)模的子數(shù)組（比如長度小于15）一般可以將歸并排序的運(yùn)行時(shí)間縮短10%~15%屋剑。

思考：

1. 為什么能縮短時(shí)間？
2. 為什么使用插入排序仇轻，使用選擇排序行嗎逆粹？（穩(wěn)定排序的角度想一下）

import java.io.File;
import java.net.URL;
import java.util.Scanner;

/**
 * Created by admin on 2016/11/20.
 */
public class Merge {
    private static Comparable[] aux;

    //一趟歸并别凹，前提a[lo,mid]有序 ,a(mid,hi]有序
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        // (lo,mid)(mid,hi)
        int i = lo, j = mid + 1;
        for (int k = lo; k < hi; k++) {
            aux[k] = a[k];
        }
        for (int k = lo; k < hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = a[j++];
            else a[k] = aux[i++];
        }
    }

    //歸并排序算法實(shí)現(xiàn)(自頂向下)
    public static void mergeSort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        mergeSort(a, 0, N);
    }

    private static void mergeSort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    //歸并排序算法實(shí)現(xiàn)邓厕，自下向上
    private static void mergeSortUP(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        //
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N));
            }
        }
    }
    //
    public static void sort(Comparable[] a) {
        mergeSort(a);
    }

    //判斷兩個數(shù)字的大小 v < w : true
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    //交換兩個數(shù)
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    //
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    //檢查a是否有序，用于對排序后的數(shù)據(jù)檢測
    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) return false;
        }
        return true;
    }

    private static String[] readDataFromFile(String fileName) throws Exception {
        /*
         *從data.in中讀取數(shù)據(jù)扁瓢，然后把數(shù)據(jù)轉(zhuǎn)換成Integer(包裝了有Comparable接口)
         */
        URL url = Merge.class.getClassLoader().getResource(fileName);
        File file = new File(url.getPath());
        Scanner sc = new Scanner(file);

        String str = sc.nextLine();
        return str.split(" ");
    }

    public static void main(String[] args) throws Exception {
        //設(shè)計(jì)成從文件讀入數(shù)據(jù)详恼，然后把數(shù)據(jù)(maven下，數(shù)據(jù)放在resources目錄)
        String[] ss = readDataFromFile("ch02/data.in");

        int N = ss.length;
        Integer[] arr = new Integer[N];
        for (int i = 0; i < N; i++) {
            arr[i] = new Integer(Integer.parseInt(ss[i]));
        }

        sort(arr);
        //    assert isSorted(arr);
        show(arr);
    }
}