思路

之前我們從選擇排序，到選擇排序的穩定性優化，到冒泡排序，到插入排序，到插入排序的提前截止時間，到希爾排序，雖然逐步一直都在優化，但是時間復雜度還是N得平方，力扣提交的結果一直都是時間超時，因為時間復雜度并沒有發生量級級別的減少，都是通過常規的優化思維，說白一點，就是沒有創新的優化點，都是一步一步，一點一點優化，想方設法能能提高一點效率就提高一點。
那么從快速排序就是要開始坐飛機了往前沖了，直接打破一個量級的時間復雜度，從N的平方，到Nlogn，N就是二叉樹的深度，logn就是每一層的時間復雜度。
為什么說快速排序是結合了二叉樹前序遞歸思想的排序，后面我把快速排序的代碼寫出來嗎，你對比一下二叉樹的前序遍歷，結構基本都是差不多的。
快速排序的解題思路就是：一般默認選擇第一個數組元素作為起點，將第一個元素處理一下，使得左邊的元素都小于它，右邊的元素都大于它。第二就開最左右的數組繼續處理，左邊的數據選擇當前第一個元素再左邊找到位置是的左邊都小于它，右邊的都大于它，右邊同理。你看這不就是二叉樹的前序遞歸遍歷嗎？
接下來直接看代碼，如果說你明白了在快排中使用到了二叉樹的前序遍歷思想，那你成功的解決了50的問題，剩下的50%是看你嫩不能解決數組中的一個點，如何找到它所在的位置，并且交換好數據嗎，這個還需要主要的是一個數組的邊界問題（如果數組題好好刷了，知道數組邊界的處理，不混亂），那第二個難點也就不是什么難點，我還是講一下找到中間位置的函數的思路吧，但是邊界為就不講了，這塊兒還是有點技巧的，回頭再來刷這個題目的時候再看吧

代碼

class Solution {public int[] sortArray(int[] nums) {sort(nums,0,nums.length-1);return nums;}//定義一個遞歸遍歷的函數sortvoid sort(int[] nums,int lo,int hi){if(lo > hi){return;}int p = partition(nums, lo, hi);sort(nums,lo,p-1);sort(nums,p+1,hi);}//定義一個找到位置的partition函數int partition(int[] nums, int lo, int hi){int pivot = nums[lo];// 關于區間的邊界控制需格外小心，稍有不慎就會出錯// 我這里把 i, j 定義為開區間，同時定義：// [lo, i) <= pivot；(j, hi] > pivot// 之后都要正確維護這個邊界區間的定義int i = lo + 1, j = hi;// 當 i > j 時結束循環，以保證區間 [lo, hi] 都被覆蓋while (i <= j) {while (i < hi && nums[i] <= pivot) {i++;// 此 while 結束時恰好 nums[i] > pivot}while (j > lo && nums[j] > pivot) {j--;// 此 while 結束時恰好 nums[j] <= pivot}if (i >= j) {break;}// 此時 [lo, i) <= pivot && (j, hi] > pivot// 交換 nums[j] 和 nums[i]swap(nums, i, j);// 此時 [lo, i] <= pivot && [j, hi] > pivot}// 最后將 pivot 放到合適的位置，即 pivot 左邊元素較小，右邊元素較大swap(nums, lo, j);return j;}// 原地交換數組中的兩個元素private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

這個運行后還是超出運行限制，到底是哪里還可以繼續優化呢，肯定是可以的，我們先不糾結了，能和面試官談到這里，說不定他還沒有懂得深的。差不多了，優化的點我先提一下，就是在上面的基礎上加了一個洗牌算法
直接看代碼：

class Solution {public int[] sortArray(int[] nums) {// 為了避免出現耗時的極端情況，先隨機打亂shuffle(nums);sort(nums,0,nums.length-1);return nums;}//定義一個遞歸遍歷的函數sortvoid sort(int[] nums,int lo,int hi){if(lo > hi){return;}int p = partition(nums, lo, hi);sort(nums,lo,p-1);sort(nums,p+1,hi);}//定義一個找到位置的partition函數int partition(int[] nums, int lo, int hi){int pivot = nums[lo];// 關于區間的邊界控制需格外小心，稍有不慎就會出錯// 我這里把 i, j 定義為開區間，同時定義：// [lo, i) <= pivot；(j, hi] > pivot// 之后都要正確維護這個邊界區間的定義int i = lo + 1, j = hi;// 當 i > j 時結束循環，以保證區間 [lo, hi] 都被覆蓋while (i <= j) {while (i < hi && nums[i] <= pivot) {i++;// 此 while 結束時恰好 nums[i] > pivot}while (j > lo && nums[j] > pivot) {j--;// 此 while 結束時恰好 nums[j] <= pivot}if (i >= j) {break;}// 此時 [lo, i) <= pivot && (j, hi] > pivot// 交換 nums[j] 和 nums[i]swap(nums, i, j);// 此時 [lo, i] <= pivot && [j, hi] > pivot}// 最后將 pivot 放到合適的位置，即 pivot 左邊元素較小，右邊元素較大swap(nums, lo, j);return j;}// 原地交換數組中的兩個元素private static void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}// 洗牌算法，將輸入的數組隨機打亂private static void shuffle(int[] nums) {Random rand = new Random();int n = nums.length;for (int i = 0 ; i < n; i++) {// 生成 [i, n - 1] 的隨機數int r = i + rand.nextInt(n - i);swap(nums, i, r);}}
}

加上洗牌算法果然就通過了

接下來就繼續分析一下，為什么加了一個洗牌算法就能提交通過呢，這里面到底優化什么？
這個問題要從快速排序的構造思想和極端情況兩方面進行分析：
首先是上面我們提到的快速排序的構造思想就是二叉數的前序遍歷構造思想，不是非常極端的二叉樹情況，那么快速排序正常的復雜度就是NlogN,但是如果運氣不好，出現了前序遍歷后的二叉樹呈現一邊倒的趨勢，這樣的話，復雜度就又變成最壞的情況，N的平方了。所以提交才沒有過。
之后我們又采用了洗牌算法，先把數組打亂，這樣就不會出現極端情況了，至于洗牌算法是什么思想，怎么實現，后續慢慢道來。