# 0912. 排序數組 ## 題目地址(912. 排序數組) <https://leetcode-cn.com/problems/sort-an-array/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個整數數組 nums，請你將該數組升序排列。 示例 1： 輸入：nums = [5,2,3,1] 輸出：[1,2,3,5] 示例 2： 輸入：nums = [5,1,1,2,0,0] 輸出：[0,0,1,1,2,5] 提示： 1 <= nums.length <= 50000 -50000 <= nums[i] <= 50000 ``` ``` ## 前置知識 - 數組 - 排序 ## 公司 - 阿里 - 百度 - 字節 ## 思路 這是一個很少見的直接考察`排序`的題目。 其他題目一般都是暗含`排序`，這道題則簡單粗暴，直接讓你排序。 并且這道題目的難度是`Medium`， 筆者感覺有點不可思議。 我們先來看題目的限制條件，這其實在選擇算法的過程中是重要的。 看到這道題的時候，大腦就閃現出了各種排序算法， 這也算是一個復習`排序算法`的機會吧。 題目的限制條件是有兩個，第一是元素個數不超過10k，這個不算大。 另外一個是數組中的每一項范圍都是`-50k`到`50k`（包含左右區間）。 看到這里，基本我就排除了時間復雜度為O(n^2)的算法。 > 我沒有試時間復雜度 O(n^2) 的解法，大家可以試一下，看是不是會TLE。 剩下的就是基于比較的`nlogn`算法，以及基于特定條件的O(n)算法。 由于平時很少用到`計數排序`等O(n)的排序算法，一方面是空間復雜度不是常量，另一方面是其要求數據范圍不是很大才行，不然會浪費很多空間。 但是這道題我感覺可以試一下。 在這里，我用了兩種方法，一種是`計數排序`，一種是`快速排序`來解決。 大家也可以嘗試用別的解法來解決。 ### 解法一 - 計數排序 時間復雜度O(n)空間復雜度O(m) m 為數組中值的取值范圍，在這道題就是`50000 * 2 + 1`。 我們只需要準備一個數組取值范圍的數字，然后遍歷一遍，將每一個元素放到這個數組對應位置就好了， 放的規則是`索引為數字的值，value為出現的次數`。 這樣一次遍歷，我們統計出了所有的數字出現的位置和次數。 我們再來一次遍歷，將其輸出到即可。  ### 解法二 - 快速排序 快速排序和歸并排序都是分支思想來進行排序的算法， 并且二者都非常流行。 快速排序的核心點在于選擇軸元素。 每次我們將數組分成兩部分，一部分是比pivot（軸元素）大的，另一部分是不比pivot大的。 我們不斷重復這個過程， 直到問題的規模縮小的尋常（即只有一個元素的情況）。 快排的核心點在于如何選擇軸元素，一般而言，選擇軸元素有三種策略： - 數組最左邊的元素 - 數組最右邊的元素 - 數組中間的元素（我采用的是這種，大家可以嘗試下別的） - 數組隨機一項元素  (圖片來自： <https://www.geeksforgeeks.org/quick-sort/>) > 圖片中的軸元素是最后面的元素，而提供的解法是中間元素，這點需要注意，但是這并不影響理解。 ## 關鍵點解析 - 排序算法 - 注意題目的限制條件從而選擇合適的算法 ## 代碼 計數排序： 代碼支持： JavaScript ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number[]} */</span> <span class="hljs-keyword">var</span> sortArray = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> counts = <span class="hljs-params">Array</span>(<span class="hljs-params">50000</span> * <span class="hljs-params">2</span> + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); <span class="hljs-keyword">const</span> res = []; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">const</span> num <span class="hljs-keyword">of</span> nums) counts[<span class="hljs-params">50000</span> + num] += <span class="hljs-params">1</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i <span class="hljs-keyword">in</span> counts) { <span class="hljs-keyword">while</span>(counts[i]--) { res.push(i - <span class="hljs-params">50000</span>) } } <span class="hljs-keyword">return</span> res; }; ``` ``` 快速排序： 代碼支持： JavaScript ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">swap</span>(<span class="hljs-params">nums, a, b</span>) </span>{ <span class="hljs-keyword">const</span> temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">nums, start, end</span>) </span>{ <span class="hljs-keyword">if</span> (start >= end) <span class="hljs-keyword">return</span>; <span class="hljs-keyword">const</span> pivotIndex = start + ((end - start) >>> <span class="hljs-params">1</span>) <span class="hljs-keyword">const</span> pivot = nums[pivotIndex] <span class="hljs-keyword">let</span> i = start; <span class="hljs-keyword">let</span> j = end; <span class="hljs-keyword">while</span> (i <= j) { <span class="hljs-keyword">while</span> (nums[i] < pivot) i++; <span class="hljs-keyword">while</span> (nums[j] > pivot) j--; <span class="hljs-keyword">if</span> (i <= j) { swap(nums, i, j); i++; j--; } } helper(nums, start, j); helper(nums, i, end); } <span class="hljs-title">/** * @param {number[]} nums * @return {number[]} */</span> <span class="hljs-keyword">var</span> sortArray = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ helper(nums, <span class="hljs-params">0</span>, nums.length - <span class="hljs-params">1</span>); <span class="hljs-keyword">return</span> nums; }; ``` ``` ## 擴展 - 你是否可以用其他方式排序算法解決 ## 參考 - [QuickSort - geeksforgeeks](https://www.geeksforgeeks.org/quick-sort/)