排序-真的了解快速排序了嗎，請解答下題
- 2019 年 10 月 10 日
- 筆記
題目
給出一個區間的集合，請合併所有重疊的區間。 示例：[[1,5],[2,7],[,10,18],[,17,19]] 結果：[[1,7],[10,19]] 為什麼呢？[1,5] [2,7]有重疊3,4；[10,18],[17,19]有重疊17,18
我們分析上面的示例，其實比較的就是下一個區間起始值是否在上一個區間的範圍內，依次比較，直到匹配失敗，就把這個已經匹配過的最小值和最大值放入一個新的區間。
基於上面的思路，我們首先得保證區間是有序的（基於起始值的有序），所以先排序，這裡我們學習一下快速排序演算法。
快速排序
快速排序核心原理是經過一趟排序之後，使得這一組數據在某個值左邊全是小於這個值的，在這個值的右邊全是大於這個值的，然後遞歸排序左邊的數組和右邊數組，直到最後數組的大小是1，排序終止，如下圖，
- 第一次我們選取值為8的元素為中間值，經過一趟排序後，4的左邊是7,2，右邊是15
- 第二次我們對左邊元素7,2,右邊元素15進行排序，選取的中間值分別是7，15
- 第三次排序完成後,2,7有序，15隻有一個元素，右邊的數組終止排序
- 第四次對2，7進行排序，2，7各只有一個元素，終止排序
結合上面的題目我們用程式碼實現快速排序
總結一下快速排序
快速排序是最常用的一種排序演算法，在實際場景中也廣泛用到，比如類庫中（jdk類庫，golang類庫）其排序演算法都有用到快速排序。
- 快速排序使用了遞歸演算法，每次分區之後，數組都會被切分成兩個大小差不多相等的小區間，直到區間大小為1，這個過程需要log(n)次，每個區間進行排序需要遍歷n（數組的結尾-開始）次，所以時間複雜度是nlog(n)，極端情況下會退化成n2,例如[1,2,3,4,5],這種情況下，數組是有序的，假設我們選的分區值是1，每次分區後兩個數組的大小差距太大（數組長度-2），，所以需要執行n次分區操作，那麼時間複雜度會退化成n2。
- 他是一種原地排序演算法，不會佔用多餘的空間，排序過程中除了申請一些臨時變數存儲，並無其它任何記憶體開銷，所以空間複雜度是O(1),
- 他是一種不穩定的排序演算法 ，因為在分區函數中會對數據元素做交換
- 快速排序的核心思想是分區和分治，分區時分區的值選取也很關鍵，一般採用中位數
快速排序的平均時間複雜度是nlog(n),其退化到n2的概率是非常小的，我們也可以選取合適的中間值進行避免，但他的原地排序，分治思想是非常優秀的，所以他在實際場景中應用廣泛。
再回到一開始的問題
我們對intervals二位數組按下標為0的元素進行了升序排序，我們按照上面的解題思路開始實現程式碼
