快速串講校招高頻面試題——排序演算法和複雜度
- 2021 年 4 月 20 日
- 筆記
在校招面試中，排序演算法是經常被問到的。排序演算法又比較多，很容易遺忘和混淆。建議收藏起來，面試前可以快速過一遍。正所謂：臨陣磨槍，不快也光。
冒泡排序
重複地遍歷要排序的數組，一次比較前後兩個數，如果它們的順序錯誤就把它們交換過來。因為越小的數會在交換過程中慢慢「浮」到數組的頂端，所以被稱作冒泡排序。具體過程如下：
- 比較相鄰的數，如果第一數個比第二數個大，就交換它們兩個。
- 對每一對相鄰數作同樣的上述操作，從開始第一對到結尾的最後一對，這樣在最後的數就是最大的數。
- 針對所有的數重複上面的步驟，除了最後一個數（因為最後一個數已經是最大的了）。
- 對越來越少的數重複步驟上面的步驟，直到整個數組排序完成。
文章持續更新，微信搜索「萬貓學社」第一時間閱讀，關注後回復「電子書」，免費獲取12本Java必讀技術書籍。
快速排序
通過一次排序將待排序的數組分隔成兩個子數組，一個子數組的數都比另一子數組的數小，則可分別對這兩部分繼續進行排序，最後使整個數組都有序。具體過程如下：
- 選擇一個基準數，通常是數組的第1個數。
- 重新排序數組，所有數比基準數小的挪放在基準數前面，所有數比基準數大的挪在基準數的後面。
- 在這個排序之後，該基準數就處於數組有序後的正確位置。
- 把基準數前後兩個子數組，按照上述步驟繼續排序，直到整個數組有序。
插入排序
在要排序的數組中，先把第1個位置數看成是一個有序的子數組，然後從第2個數逐個進行插入，直到整個數組有序為止。
希爾排序
希爾排序是插入排序的升級版本，先把整個數組分割為幾個子數組進行插入排序，當整個數組中的數基本有序時，再對整個數組進行一次插入排序。具體過程如下：
- 選擇一個增量序列t1，t2，…，tk，其中ti > tj，tk = 1。比如：40、13、4、1。
- 按增量序列個數k，對序列進行k次插入排序。
- 每次插入排序，根據對應的增量ti，將數組分割成幾個子序列，分別對各子數組進行插入排序。當最後增量為1 時，對整個數組作進行一次插入排序。
選擇排序
在要排序的數組中，首先找出最小的一個數和第1個位置的數交換；然後在剩下的數中再找最小的數和第2個位置的數交換；依次類推，直到倒數第二個數和最後一個數進行比較為止。
文章持續更新，微信搜索「萬貓學社」第一時間閱讀，關注後回復「電子書」，免費獲取12本Java必讀技術書籍。
堆排序
堆排序是利用堆這種數據結構所設計的一種排序演算法。堆排序可以分為兩個階段：堆的構造階段、下沉排序階段。
在堆的構造階段中，我們將原始數組重新組織安排進一個堆中；然後在下沉排序階段，我們從堆中按遞減順序取出所有元素並得到排序結果。
歸併排序
把兩個有序的數組合併成一個有序的數組。也就是說，把要排序的數組分成兩個子數組，當每個子數組是有序的時候，再把這兩個子數組合併成為整個數組，也叫做二路歸併排序。如果把要排序的數組分成多個子數組，就叫做多路歸併排序。
計數排序
計數排序使用了一個額外的數組 ，其中第i個數是待排序數組中數等於i的個數。然後根據這個額外的數組來將待排序數組中的數排到正確的位置。
桶排序
桶排序是將待排序數組分到有限數量的桶里，然後再使用桶排序或者其他的排序演算法對每個桶再分別進行排序。
基數排序
基數排序是把整數按位數切割成不同的數字，然後按每個位數分別比較。按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。
文章持續更新，微信搜索「萬貓學社」第一時間閱讀，關注後回復「電子書」，免費獲取12本Java必讀技術書籍。
排序演算法總結
複雜度總結
| 排序演算法 | 時間複雜度(平均) | 時間複雜度(最壞) | 時間複雜度(最好) | 空間複雜度 | 穩定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | √ |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | × |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | √ |
| 希爾排序 | O(n log n) | O(n²) | O(n) | O(1) | × |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | × |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | × |
| 歸併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | √ |
| 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | √ |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | √ |
| 基數排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | √ |
微信公眾號：萬貓學社
微信掃描二維碼
關注後回復「電子書」
獲取12本Java必讀技術書籍
