歸并排序

思路：

歸并排序?qū)儆谕獠颗判颍驗(yàn)樵诤喜r(shí)，需要一個(gè)額外的數(shù)組。將待排序數(shù)據(jù)分成兩部分，繼續(xù)將兩個(gè)子部分進(jìn)行遞歸的歸并排序；然后將已經(jīng)有序的兩個(gè)子部分進(jìn)行合并，最終完成排序。

復(fù)雜度分析：

平均時(shí)間復(fù)雜度為O(nlogn)，遞歸調(diào)用間接使用了輔助數(shù)組，需要額外的O(n)空間進(jìn)行臨時(shí)存儲(chǔ)。故空間復(fù)雜度為O(n)

這里面要注意，求兩個(gè)數(shù)的中點(diǎn)時(shí)，注意溢出問(wèn)題

int mid =(head + rear) / 2;

這種方法不安全，當(dāng)數(shù)很大的時(shí)候，(head + rear)可能會(huì)大于int最大值，導(dǎo)致溢出，所以可以考慮下面這種方式：

int mid =head  + (head + rear)/ 2;

public class MergeSort {
    /**
     * 歸并排序算法
     * @param list     待排序的列表
     * @param tempList 臨時(shí)列表
     * @param head     列表開(kāi)始位置
     * @param rear     列表結(jié)束位置
     */
    public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
        if (head < rear) {
            // 取中間值
            int middle =head  + (head + rear)/ 2;
            // 遞歸劃分列表的左序列
            mergeSort(list, tempList, head, middle);
            // 遞歸劃分列表的右序列
            mergeSort(list, tempList, middle + 1, rear);
            // 合并列表
            merge(list, tempList, head, middle + 1, rear);
        }
    }

    /**
     * 合并操作(列表的兩兩合并)
     */
    public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
        // 左指針尾
        int headEnd = middle - 1;
        // 右指針頭
        int rearStart = middle;
        // 臨時(shí)列表的下標(biāo)
        int tempIndex = head;
        // 列表合并后的長(zhǎng)度
        int tempLength = rear - head + 1;

        // 先循環(huán)兩個(gè)區(qū)間段都沒(méi)有結(jié)束的情況
        while ((headEnd >= head) && (rearStart <= rear)) {
            // 如果發(fā)現(xiàn)右序列大，則將此數(shù)放入臨時(shí)列表
            if (list[head] < list[rearStart]) {
                tempList[tempIndex++] = list[head++];
            } else {
                tempList[tempIndex++] = list[rearStart++];
            }
        }

        // 判斷左序列是否結(jié)束
        while (head <= headEnd) {
            tempList[tempIndex++] = list[head++];
        }

        // 判斷右序列是否結(jié)束
        while (rearStart <= rear) {
            tempList[tempIndex++] = list[rearStart++];
        }

        // 交換數(shù)據(jù)
        for (int i = 0; i < tempLength; i++) {
            list[rear] = tempList[rear];
            rear--;
        }
    }
}