在校招面試中，排序演算法是經常被問到的，排序演算法又比較多，很容易遺忘和混淆，建議收藏起來，面試前可以快速過一遍，正所謂：臨陣磨槍，不快也光，
冒泡排序
重復地遍歷要排序的陣列，一次比較前后兩個數，如果它們的順序錯誤就把它們交換過來，因為越小的數會在交換程序中慢慢“浮”到陣列的頂端，所以被稱作冒泡排序，具體程序如下：
- 比較相鄰的數，如果第一數個比第二數個大，就交換它們兩個，
- 對每一對相鄰數作同樣的上述操作，從開始第一對到結尾的最后一對，這樣在最后的數就是最大的數，
- 針對所有的數重復上面的步驟，除了最后一個數（因為最后一個數已經是最大的了），
- 對越來越少的數重復步驟上面的步驟，直到整個陣列排序完成，
快速排序
通過一次排序將待排序的陣列分隔成兩個子陣列，一個子陣列的數都比另一子陣列的數小，則可分別對這兩部分繼續進行排序，最后使整個陣列都有序，具體程序如下：
- 選擇一個基準數，通常是陣列的第1個數，
- 重新排序陣列，所有數比基準數小的挪放在基準數前面，所有數比基準數大的挪在基準數的后面，
- 在這個排序之后，該基準數就處于陣列有序后的正確位置，
- 把基準數前后兩個子陣列，按照上述步驟繼續排序，直到整個陣列有序，
插入排序
在要排序的陣列中，先把第1個位置數看成是一個有序的子陣列，然后從第2個數逐個進行插入，直到整個陣列有序為止，
希爾排序
希爾排序是插入排序的升級版本，先把整個陣列分割為幾個子陣列進行插入排序，當整個陣列中的數基本有序時，再對整個陣列進行一次插入排序，具體程序如下：
- 選擇一個增量序列t1，t2，…，tk，其中ti > tj，tk = 1，比如：40、13、4、1，
- 按增量序列個數k，對序列進行k次插入排序，
- 每次插入排序，根據對應的增量ti，將陣列分割成幾個子序列，分別對各子陣列進行插入排序，當最后增量為1 時，對整個陣列作進行一次插入排序，
選擇排序
在要排序的陣列中，首先找出最小的一個數和第1個位置的數交換；然后在剩下的數中再找最小的數和第2個位置的數交換；依次類推，直到倒數第二個數和最后一個數進行比較為止，
堆排序
堆排序是利用堆這種資料結構所設計的一種排序演算法，堆排序可以分為兩個階段：堆的構造階段、下沉排序階段，
在堆的構造階段中，我們將原始陣列重新組織安排進一個堆中；然后在下沉排序階段，我們從堆中按遞減順序取出所有元素并得到排序結果，
歸并排序
把兩個有序的陣列合并成一個有序的陣列，也就是說，把要排序的陣列分成兩個子陣列，當每個子陣列是有序的時候，再把這兩個子陣列合并成為整個陣列，也叫做二路歸并排序，如果把要排序的陣列分成多個子陣列，就叫做多路歸并排序，
計數排序
計數排序使用了一個額外的陣列 ，其中第i個數是待排序陣列中數等于i的個數，然后根據這個額外的陣列來將待排序陣列中的數排到正確的位置，
桶排序
桶排序是將待排序陣列分到有限數量的桶里，然后再使用桶排序或者其他的排序演算法對每個桶再分別進行排序，
基數排序
基數排序是把整數按位數切割成不同的數字，然后按每個位數分別比較，按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位，
排序演算法總結
復雜度總結
| 排序演算法 | 時間復雜度(平均) | 時間復雜度(最壞) | 時間復雜度(最好) | 空間復雜度 | 穩定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | √ |
| 快速排序 | O(n log n) | O(n2) | O(n log n) | O(log n) | × |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | √ |
| 希爾排序 | O(n log n) | O(n2) | O(n) | O(1) | × |
| 選擇排序 | O(n2) | O(n2) | O(n2) | 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(n2) | O(n + k) | √ |
| 基數排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | √ |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/275492.html
標籤：其他