題目連結：
題目意譯：
給定一個整數陣列 nums，將該陣列以升序順序排序並回傳。
你需要在不使用任何內建函式、在時間複雜度為 O(nlog(n)) 以及空間複雜度盡可能小的情況下來解出本題。
限制：
1 ≦ nums.length ≦ 5 × 10 ^ 4
-5 × 10 ^ 4 ≦ nums[i] ≦ 5 × 10 ^ 4
範例測資：
範例 1：
輸入： nums = [5,2,3,1]
輸出： [1,2,3,5]
解釋： 將陣列排序後，有些數字的位置沒有改變（例如 2 和 3），而其他則數字則有所改變（例如 1 和 5）。
範例 2：
輸入： nums = [5,1,1,2,0,0]
輸出： [0,0,1,1,2,5]
解釋： 注意到 nums 中的數字不一定彼此相異。
解題思維：
可以看到這題就是可以練習各種排序演算法的題目。
合併排序法（Merge Sort）：這題有稍微講述過。最糟時間複雜度為 O(nlog(n))，「額外」空間複雜度則為 O(n)。範例程式碼即是採取此演算法。
（注：這邊標記「額外」是因為如果算上輸入本身，大部分的演算法（不只是排序演算法而已）的空間複雜度都至少是 O(n)。當然這個「n」實際上也要看題目的定義，但大部分牽扯到陣列的基本上就會屬於這一群演算法。）
不過合併排序也有原地（In-place）排序的變體，意即只使用陣列本身的空間來處理這些「交換」或「數值更動」（但當然，可以有其他的 O(1) 個指標、變數等存在著）。可以參見英文維基頁面來得到更多資訊，以及參見 Geeksforgeeks 網頁來看其中若干個的實作方式。
快速排序法（Quick Sort）：這題講到的是快速選擇法（Quick Select），但實際上差別只在於快速選擇法是要找數字，因此只會選其中一邊遞迴；而快速排序因為需要「排序」，所以兩邊都要遞迴。因為每次都會選某個基準值（Pivot）來將現在的陣列分成左右兩邊，其中左邊是小於基準值的數字、右邊是大於基準值的數字（等於基準值可以隨便放在左右兩邊的某一側）。因此一直遞迴來分群分到最後整個陣列便會按升序排序。最糟時間複雜度為 O(n ^ 2)（例如說每次都選到最小值或最大值等），但平均時間複雜度為 O(nlog(n))；而「額外」空間複雜度為 O(1)（但是如果算上遞迴空間，則應為 O(log n)）。
基數排序法（Radix Sort）：這題已經完整介紹過了。時間複雜度和「額外」空間複雜度為 O(n)。
計數排序法（Counting Sort）：這題也介紹過了。計數排序法的「額外」空間複雜度與時間複雜度是相等的，並且是被數值範圍所決定。而本題的數值範圍為 -5 × 10 ^ 4 ≦ nums[i] ≦ 5 × 10 ^ 4，所以我們會需要一個大小為 10 ^ 5 + 1 的陣列來統計所有每一種的數字。
……還有很多神秘的演算法，族繁不及備載。
如果有興趣的話，可以參考這個影片
。裡面有視覺化的動畫以及解說（不過是英文的）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
