1 題目

題目：Sort Integer II

lintcode題號——464，難度——easy

描述：給一組整數，請將其在原地按照升序排序。可使用歸并排序，快速排序，堆排序或者任何其他O(n*log n)的排序算法。

樣例1：

輸入：[3,2,1,4,5]，
輸出：[1,2,3,4,5]。

樣例2：

輸入：[2,3,1]，
輸出：[1,2,3]。

2 思路

??歸并排序基于分治法，將復雜的大問題分解成足夠簡單的小問題，分而治之。先進行分解的步驟，將原本無序的序列至頂向下不斷進行二分，直到不可再分，即每個分組都只剩一個元素;之后進行合并的步驟，將分組按照原來拆分的過程，兩兩合并，在合并的過程中需要按照升序或者降序的需求對元素進行比較，使得合并后的每個小序列都是有序的，直到合并成完整的大序列。

歸并排序的步驟：

1. 將序列不斷向下二分；
2. 直到不可再分，每個分組只有單個元素；（此時每個分組都是有序的）
3. 將有序分組兩兩向上合并成有序；（合并兩個有序數組）
4. 直到所有分組合并成完整的序列。

??關于將兩個原本就有序（假設升序）的分組合并成一個完整有序的分組，我們只需要依次比較分組的頭元素，每次都將較小的元素有序放入新分組，最后一定有一個分組先放完，另一個分組剩下若干個元素，直接將不為空的分組剩余元素（原本就是有序的）放入新分組，這樣新分組里的元素就全部都是有序的了。

合并兩個有序數組的步驟：（新數組存放合并后的結果）

1. 比較兩個數組的頭元素；
2. 將較小的元素從原數組中取出，放入新數組；
3. 重復上述1、2步驟，直到兩個數組中的一個為空；
4. 將另一個不為空的數組所有元素放入新數組；
5. 此時的新數組內的元素即為有序的。

2.1 圖解

合并兩個有序數組的流程：

歸并排序的流程：

2.2 時間復雜度

??歸并排序使用遞歸實現，對包含n個元素的數組，計算其時間復雜度，先分析拆分過程：

第一層將n個數劃分為2個分組，每個分組包含n/2個元素；
第二層將n個數劃分為4個分組，每個分組包含n/4個元素；
第三層將n個數劃分為8個分組，每個分組包含n/8個元素；
……
第log n層將n個數劃分為n個分組，每個分組包含1個元素。

??再看合并過程：

第log n層將n分組合并成n/2個分組，每個元素都會被遍歷一次，每個元素耗時O(1)，該層耗時O(n)；
……
第3層將8分組合并成4個分組，每個元素都會被遍歷一次，每個元素耗時O(1)，該層耗時O(n)；
第2層將4分組合并成2個分組，每個元素都會被遍歷一次，每個元素耗時O(1)，該層耗時O(n)；
第1層將2分組合并成1個分組，每個元素都會被遍歷一次，每個元素耗時O(1)，該層耗時O(n)；

??所以每層耗時為O(n)，層數為log n，算法的時間復雜度為O(n*log n)。

2.3 空間復雜度

??算法不能原地排序，需要用到一個與原數組一樣大的空間用來存放臨時數據，算法的空間復雜度為O(n)。

3 源碼

??注意事項：

1. 需要使用一個臨時數組，存放每次遞歸過程中合并兩個有序數組之后的結果，排序完成再復制會原數組，否則直接原地排序會打亂原數組的元素。
2. 歸并排序是遞歸算法，注意遞歸的三要素，防止死循環。
3. 合并有序數組時候，需要注意左右兩個數組的起點位置。

??C++版本：

/**
* @param A: an integer array
* @return: nothing
*/
void sortIntegers2(vector<int> &A) {
    // write your code here
    if (A.size() <= 1)
    {
        return;
    }

    vector<int> temp(A.size());
    mergeSort(A, 0, A.size() - 1, temp);
}

// 遞歸的定義
void mergeSort(vector<int> & A, int start, int end, vector<int> & temp)
{
    if (start >= end) // 遞歸的出口
    {
        return;
    }

    int mid = start + (end - start) / 2; // 取中點
    mergeSort(A, start, mid, temp); // 遞歸的拆解
    mergeSort(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp);
}

// 合并有序數組
void merge(vector<int> & A, int start, int mid, int end, vector<int> & temp)
{
    int left = start;
    int right = mid + 1; // 注意此處的起點是中點的下一個元素
    int index = start;
    while (left <= mid && right <= end)
    {
        if (A.at(left) < A.at(right))
        {
            temp.at(index++) = A.at(left++);
        }
        else
        {
            temp.at(index++) = A.at(right++);
        }
    }

    while (left <= mid)
    {
        temp.at(index++) = A.at(left++);
    }
    while (right <= end)
    {
        temp.at(index++) = A.at(right++);
    }

    // 將臨時數組中排好序的元素復制會原數組
    for (int i = start; i <= end; i++)
    {
        A.at(i) = temp.at(i);
    }
}