| 算法 | 簡述 | 邏輯做法 | 最壞 | 平均 | 最好 | 空間複雜度 | 穩定性 | 複雜性 | 重點 | 測試(100000) | 實際效率（以随機下冒泡為基準） | 優點缺點 | 評價 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 冒泡 | 冒泡排序(Bubble Sort)，又被稱為氣泡排序或泡沫排序。 它是一種較簡單的排序算法。它會周遊若幹次要排序的數列，每次周遊時，它都會從前往後依次的比較相鄰兩個數的大小；如果前者比後者大，則交換它們的位置。這樣，一次周遊之後，最大的元素就在數列的末尾！ 采用相同的方法再次周遊時，第二大的元素就被排列在最大元素之前。重複此操作，直到整個數列都有序為止！ | 兩層循環。 1.第一層從後往前，第二層從前往後，直到第一層的index，這樣每輪選出最大的數，同時隻比較到上輪最大數之前的數。 2.内層循環則進行比較，判斷是否需要交換。 | O(n²) 逆序 | O(n²) | O(n) 順序，相同 | O(1) | 穩定 | 簡單 | 1.比較不需要每輪都到底。 2.每輪比較發現沒有需要交換的，說明已經有序，直接跳出。 | 升序：3 降序：15670 重複：0 随機：18347 | 升序：100% 降序：100% 重複：100% 随機：100% | ||
| 插入 | 直接插入排序(Straight Insertion Sort)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表。開始時有序表中隻包含1個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，将它插入到有序表中的适當位置，使之成為新的有序表，重複n-1次可完成排序過程。 | 兩層循環，下标1的數已經有序，是以第一層從1開始，用臨時變量儲存待插入的數組值，第二層循環從後往前依次比較，判斷是否交換，直到待比較數組值小于臨時變量為止break，break很重要 | 1.第二層比較必須從後往前，減少交換或者移動的次數。 2.第二層比較結束一定要break。 | 升序：3 降序：7956 重複：0 随機：1983 | 升序：100% 降序：50.8% 重複：100% 随機：10.8% | ||||||||
| 希爾 | 希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。 希爾排序實質上是一種分組插入方法。它的基本思想是：對于n個待排序的數列，取一個小于n的整數gap(gap被稱為步長)将待排序元素分成若幹個組子序列，所有距離為gap的倍數的記錄放在同一個組中；然後，對各組内的元素進行直接插入排序。 這一趟排序完成之後，每一個組的元素都是有序的。然後減小gap的值，并重複執行上述的分組和排序。重複這樣的操作，當gap=1時，整個數列就是有序的。 | 好了解的寫法，就是純按簡述邏輯寫，需要4層循環。 其實3層就可以了。 第一層控制gap，每次縮小2分之一（縮小邏輯可以換層更科學的），第二層從gap開始，每次加1。這樣就可以，不需要再分出一個循環來做每個組。加1自然覆寫到每個組了。第三層從上一層的i開始，每次比較i-gap，每次i=i-gap。其它邏輯和直接插入一緻。 像交于直接插入排序，減少了二層循環的次數 | O(n2) 1.3~2方 | O(nlog2n) | O(n1.3) | 不穩定 | 較複雜 其實代碼量比直接插入沒多幾行 | 第二層gap開始，每次加1，就能覆寫每個組了，不需要為每個組單獨開一個循環。 | 升序：13 降序：10 重複：1 随機：15 4層循環 升序：10 降序：7 重複：4 随機：14 | 升序：1000%以上 降序：0.06% 重複：1000%以上 随機：0.08% | 效率也很好，就是不穩定，如果空間有要求，且穩定性也不考慮，可以使用，如果空間沒有要求，但對穩定性有考慮，可以使用歸并排序。 | 效率平均且高效 | |
| 選擇 | 選擇排序(Selection sort)是一種簡單直覺的排序算法。 它的基本思想是：首先在未排序的數列中找到最小(or最大)元素，然後将其存放到數列的起始位置；接着，再從剩餘未排序的元素中繼續尋找最小(or最大)元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 | 兩層循環，第一層從小到大，控制二層循環每次找出最小的數，兩個臨時變量，一個儲存帶比較的“最小數組值”，一個記錄“最小數組值”的下标，二層循環結束，交換最小值下标和第一層循環的i。 | 升序：1178 降序：4463 重複：1567 随機：1531 | 升序：1000%以上 降序：28.5% 重複：1000%以上 随機：8.3% | 1.最多隻有n個交換，交換次數小。 2.時間效率比較平均，且相對算高。 | ||||||||
| 歸并 | 将兩個的有序數列合并成一個有序數列，我們稱之為"歸并"。 歸并排序(Merge Sort)就是利用歸并思想對數列進行排序。根據具體的實作，歸并排序包括"從上往下"和"從下往上"2種方式。 1. 從下往上的歸并排序：将待排序的數列分成若幹個長度為1的子數列，然後将這些數列兩兩合并；得到若幹個長度為2的有序數列，再将這些數列兩兩合并；得到若幹個長度為4的有序數列，再将它們兩兩合并；直接合并成一個數列為止。這樣就得到了我們想要的排序結果。(參考下面的圖檔) 2. 從上往下的歸并排序：它與"從下往上"在排序上是反方向的。它基本包括3步： ① 分解 -- 将目前區間一分為二，即求分裂點 mid = (low + high)/2; ② 求解 -- 遞歸地對兩個子區間a[low...mid] 和 a[mid+1...high]進行歸并排序。遞歸的終結條件是子區間長度為1。 ③ 合并 -- 将已排序的兩個子區間a[low...mid]和 a[mid+1...high]歸并為一個有序的區間a[low...high]。 | 分治加疊代。 一次疊代内分裂成兩個子疊代。分裂點為2分之1。 兩個子疊代完成後，都需要進行合并。 合并時需要零時數組來暫存。 合并邏輯“ head2 > e || (nums[head1] <= nums[head2] && head1 <= index)”。 即：在後半段指針結束或者前半段頭指針資料小于或者等于後半段頭指針資料，同時前半段頭指針還未結束，則将前半段頭指針資料加入臨時數組中，否則将後半段頭指針資料加入臨時數組中。 | O(n) | 較複雜 | 可以利用1數存兩值的技巧，将O(n)的空間複雜度優化到O(1)。 一數存兩數算法 midVal = max(a,b) + 1 在這裡延伸為 max（num[0],num[1],num[2],num[3],num[4]......）+1 temp = a + b * midVal。 a = temp % midVal b = temp / midVal | 升序：10 降序：13 重複：5 随機：11 不使用臨時數組暫存下： 升序：51 降序：39 重複：38 随機：36 | 升序：1000%以上 降序：0.08% 重複：1000%以上 随機：0.06% 不使用臨時數組暫存下： 升序：1000%以上 降序：0.24% 重複：1000%以上 随機：0.20% | 比選擇排序更加平均， 比希爾排序穩定，效率還差不多。 唯一缺點，需要一倍的臨時數組。 優化掉額外臨時數組後，效率也很好。相交于臨時數組慢了3倍 | |||||
| 桶 | 桶排序(Bucket Sort)的原理很簡單，它是将數組分到有限數量的桶子裡。 假設待排序的數組a中共有N個整數，并且已知數組a中資料的範圍[0, MAX)。在桶排序時，建立容量為MAX的桶數組r，并将桶數組元素都初始化為0；将容量為MAX的桶數組中的每一個單元都看作一個"桶"。 在排序時，逐個周遊數組a，将數組a的值，作為"桶數組r"的下标。當a中資料被讀取時，就将桶的值加1。例如，讀取到數組a[3]=5，則将r[5]的值+1。 | 需要一個數組最大值長度臨時數組，用于存儲數組每個值在臨時數組[數組值]的标記1。兩個并列循環，第一個先做一遍原數組的循環，給臨時數組[原數組值]++，第二個循環臨時數組，根據值大小，添加幾個下标到原數組中，以完成排序 | O(n+k) | O(n+m) | 原數組值作為臨時數組的下标，臨時數組某個下标值大于1，說明該下标值在原數組中出現了多次 | 升序：9 降序：3 重複：2 随機：5 | 升序：1000%以上 降序：0.02% 重複：1000%以上 随機：0.03% | 如果原數組中存在大值，該排序極耗費空間，否者該排序效率最好，而且穩定。 | 如果原數組中值都很小，該算法效率最高。 | ||||
| 基數 | 基數排序(Radix Sort)是桶排序的擴充，它的基本思想是：将整數按位數切割成不同的數字，然後按每個位數分别比較。 具體做法是：将所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。 | 外層方法控制radix變化（每次乘10）， 兩個臨時數組，第一個用于分成10個桶，另一個用于存儲排好序後的原數組。 第一個循環建構10個桶裡的資料，在用一個循環從後往前buckets[i] += buckets[i - 1];建構出每個分段最後一個數的下标。再一個循環沖後往前周遊原數組，更具桶裡存的下标，放入臨時數組，桶存的下标-1，最後将排好序的臨時數組複制給原數組。 | O(d*(n+k)) | O(n+n+k) | 最後桶裡存的是每個分段最後一個數的下标。 | 升序：24 降序：13 重複：9 随機：9 | 升序：1000%以上 降序：0.08% 重複：1000%以上 随機：0.05% | 和桶排序相比，桶數量極小了，代價是需要多做基數增長的D次，如果原數組不均勻，理論上白白浪費了很多次n+k | 還是歸并排序牛逼 | ||||
| 快排 | 快速排序(Quick Sort)使用分治法政策。 它的基本思想是：選擇一個基準數，通過一趟排序将要排序的資料分割成獨立的兩部分；其中一部分的所有資料都比另外一部分的所有資料都要小。然後，再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。 快速排序流程： (1) 從數列中挑出一個基準值。 (2) 将所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的後面(相同的數可以到任一邊)；在這個分區退出之後，該基準就處于數列的中間位置。 (3) 遞歸地把"基準值前面的子數列"和"基準值後面的子數列"進行排序。 | 分治加疊代。 一次疊代内分裂成兩個子疊代。分裂點為基數在數組中的位置。 每個疊代内，用兩個并列的循環，分别重兩端找各自的大于基數的值和小于基數的值，找到後等待交換，外面套一層循環控制什麼時候結束while(i<j)，比較時如果相等且i<j則i++，進入下一次比較，否則則交換 | O(n²) 重複，就是基數找不好 | while (i < j && base > nums[i]) { //重點一：就在這裡，因為base和nums沒有 “=” 是以方向是交替，不會出現兩邊都同時++和--。 也是以根本就不需要方向。也得出最後的num[i] = base if (nums[i] == nums[j] && i<j) { //重點二：必須有這一步，不然存在重複的數組 會有死循環。 還有點 i 必須小于 j 否則，nums[i] == nums[j] 無意義 | 升序：2571 降序：2004 重複：18554 随機：18 | 升序：1000%以上 降序：12.8% 重複：1000%以上 随機：0.10% | 都是渣渣，也就随機性能稍好點，重複下就是渣渣 | 渣渣，最怕重複 |
參考代碼：https://gitee.com/wzgdxg/ksf