912. 排序數組

合併排序

在三傻排序（選擇、插入、冒泡）當中，常常會有許多無效操作，
而合併排序中，兩個數字的比較沒有浪費，所以能讓複雜度變低。

演算法流程

1. 將一個陣列切成兩半
2. 透過這個演算法，排序好左半跟右半之後，將兩端合併。

• 合併的方法，是建立兩個指針i、j（這裡不是指C++的指針，而是指向位置的變數），分別指向左右兩邊的起點。以及暫存的空間temp，和指向temp位置的指針index。
• 因為兩邊有序，每次只需要比較兩個指針指向的數字，並放到temp中。

3. 合併完成之後，演算法結束。

程式碼

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        auto mergeSort = [&](this auto&& mergeSort, int left, int right)  -> void {
            // 終止條件
            if(left >= right) return;
            int mid = left + (right - left) / 2;
            // 排好左右
            mergeSort(left, mid);
            mergeSort(mid + 1, right);
            // 暫存區域
            vector<int> temp(right - left + 1);
            int index = 0, i = left, j = mid + 1;
            // 兩個指針分別指向左右區塊，根據大小放到暫存空間裡面
            while(i <= mid && j <= right) {
                temp[index++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
            }
            while(i <= mid) {
                temp[index++] = nums[i++];
            }
            while(j <= right) {
                temp[index++] = nums[j++];
            }
            for(int k = 0; k < right - left + 1; ++k) {
                nums[left + k] = temp[k];
            }
        };
        mergeSort(0, nums.size() - 1);
        return nums;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$

三路快速排序

把整個數組分為 $\begin{cases}<x\\=x\\>x\end{cases}$ 三塊區域，分開之後，遞迴處理 $\begin{cases}<x\\>x\end{cases}$ 的區塊就行。
在選擇 $x$ 時，從數組當中隨機選擇，這樣做的原因是避免最差情況的發生。
舉例來說，如果不是隨機選擇，而是每次都選最後一個數字作為分三路的 $x$，
如果給的數組如果是倒序的，效率就會降低成 $O(n^2)$ 。

演算法流程

1. 現在要排序 nums[0...n - 1]的數字，簡稱quickSort(0, n - 1)
   隨機選擇一個數組當中的數字 $x$。

2. 變數i遍歷整個數組，分為三個區塊，

   • 變數smaller以左的數字是<x
   • 變數greater以右是>x
   • nums[smaller...greater]則是=x的區塊。

3. 在分割時，將數字分發到對應的區塊，當小於跟大於分好時，等於的區塊自然就好了。

• 三種情況：$\begin{cases} nums[i]<x & 右移~smaller, 右移~i\\ nums[i]=x & 右移~i \\ nums[i]>x & 左移~greater, i~不變 \end{cases}$

• 遇到 $<x$ 時，將nums[i]跟nums[smaller]交換，
  由於找到小於區塊的數字，smaller增加，因為換過來的數字已經檢查過，所以i也增加。

• 遇到 $=x$ 時，單純增加 $i$ ，當遇到小數字時，有可能會被往前換。

• 遇到 $>x$ 時，將nums[i]跟nums[greater]交換，由於找到大於區塊的數字，greater減少，因為換過來的數字沒有檢查過，所以i不變。

4. 遞迴呼叫quickSort(left, smaller-1)、quickSort(greater+1, right)，
   差一是因為nums[smaller...greater]是閉區間。此時left = 0，right = n - 1。

值得一提的是，分為三路的步驟 2,3，是荷蘭國旗問題的解決方法，
提出者是Dijkstra，沒錯就是你知道的那個 Dijkstra。
A：最短路徑 Dijkstra 演算法，作業系統的信號量 Semaphore，現在的荷蘭國旗問題，三個了。

程式碼

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 將 nums[l...r] 的區塊分為 < x, = x, > x 三種
        auto partition = [&](int l, int r, int x) -> pair<int, int> {
            int smaller = l, greater = r;
            int i = l;
            while(i <= greater) {
                if(nums[i] < x) {
                    swap(nums[smaller++], nums[i++]);
                }
                else if(nums[i] > x) {
                    swap(nums[greater--], nums[i]);
                }
                else { // nums[i] == x
                    ++i;
                }
            }
            return {smaller, greater};
        };
        auto quickSort = [&](this auto&& quickSort, int l, int r) -> void {
            if(l >= r) return;
            int x = nums[l + rand() % (r - l + 1)];
            auto mid = partition(l, r, x);

            // nums[mid.first...mid.second]都 = x,
            quickSort(l, mid.first - 1); 
            quickSort(mid.second + 1, r);
            return;
        };
        quickSort(0, nums.size() - 1);
        return nums;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(\log{n})$