貌似排序是在面試中經(jīng)常出現(xiàn)的問題袖订，那么我就來復(fù)習(xí)一下吧塑顺！
- 插入排序(insertion sort)
含義：第i趟排序?qū)⑿蛄兄械趇+1個元素ki+1插入到一個已經(jīng)按值有序的子序列(k'1, k'2, ..., k'i)的合適位置嵌牺，得到一個長度為i+1罕伯，仍然有序的子序列(k''1, k''2, ..., k''i+1)。
優(yōu)化：在尋找需要插入的位置時燃观，可以采用折半查找對時間復(fù)雜度進行優(yōu)化褒脯。
- 平均時間復(fù)雜度O(n2)，采用折半查找則為O(nlogn)缆毁；
- 穩(wěn)定排序番川；
- 選擇排序(selection sort)
含義：第i趟排序從序列的后n-i+1個元素中選擇一個最小的元素與該n-i+1個元素最前的元素交換位置。
- 平均時間復(fù)雜度O(n2)脊框；
- 不穩(wěn)定排序颁督，例如(49, 38, 49', 13)，一趟排序后會變成(13, 38, 49', 49)浇雹，倆49交換了位置沉御；
- 泡排序(bubble sort)
含義：比較相鄰元素，若前者較大則交換兩元素昭灵，一趟排序后最大值換到第n個位置吠裆。注意某一趟不發(fā)生元素交換時，排序完成烂完。
- 平均時間復(fù)雜度O(n2)试疙，適用于元素基本有序的情況；
- 穩(wěn)定排序抠蚣；
- 謝爾排序(Shell's sort)
含義：又稱縮小增量排序祝旷。先確定一個間隔gap，將參加排序的序列按此間隔一次分成若干子序列嘶窄，對子序列排序怀跛，然后縮小間隔，直至gap = 1柄冲。
- 不適用于鏈表吻谋；
- 平均時間復(fù)雜度介于O(nlogn)和O(n2)之間，略大于O(nlogn)羊初；
- 不穩(wěn)定排序滨溉；
- 快速排序(quick sort)
含義：被認為是對泡排序的一種改進，又稱劃分排序法长赞。在當前參加排序的序列(ks, ks+1, ..., kt)中任選一個元素作為分界元素晦攒，將小于等于分界元素的所有元素都移到分界元素前面，把大于等于分界員素的所有元素移到分界元素后面得哆，這樣分界元素正好處于排序的最終位置脯颜，并把當前參加排序的序列劃分成了前后兩個子序列。
- 平均時間復(fù)雜度：O(nlogn)贩据；
- 不穩(wěn)定排序栋操；
- 堆排序(heap sort)
含義：是對選擇排序的一種改進。建立初始堆饱亮，取堆頂元素矾芙，交換堆的第1個元素和最后1個元素，將前n-1個元素再轉(zhuǎn)換為一個堆近上，重復(fù)取堆頂?shù)倪^程剔宪。
堆的調(diào)整方法：當把第n個元素和堆頂交換后，剩余n-1個元素除堆頂外還維持堆的特性壹无，因此將堆頂和左右孩子比較葱绒，與較大值交換，并繼續(xù)與新的左右孩子比較并進行調(diào)整斗锭。
初始堆的建立：從最后一個非孩子節(jié)點開始進行堆的調(diào)整地淀，直至堆頂。
- 不適用于鏈表岖是；
- 時間復(fù)雜度：O(nlogn)帮毁；
- 不穩(wěn)定排序；
- 歸并排序(merging sort)
含義：將兩個按值有序的序列合并成一個豺撑。
- 平均時間復(fù)雜度：O(nlogn)作箍；
- 穩(wěn)定排序；
- 桶排序(Bucket sort)
含義：將數(shù)組分到有限數(shù)量的桶子里前硫。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）胞得。
- 主要適用于均勻分布的數(shù)字數(shù)組;
- 最好情況下線性時間O(n)；
- 穩(wěn)定排序屹电；
總結(jié)：
| 編號 | 算法 | 穩(wěn)定性 | 最差時間復(fù)雜度 | 平均時間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|---|---|---|
| 1 | 插入排序 | 穩(wěn)定 | O(n2) | O(n2) | O(1) |
| 2 | 選擇排序 | 不穩(wěn)定 | O(n2) | O(n2) | O(1) |
| 3 | 泡排序 | 穩(wěn)定 | O(n2) | O(n2) | O(1) |
| 4 | 謝爾排序 | 不穩(wěn)定 | O(n2) | O(nlogn)~O(n2) | O(1) |
| 5 | 快速排序 | 不穩(wěn)定 | O(n2) | O(nlogn) | O(1) |
| 6 | 堆排序 | 不穩(wěn)定 | O(nlogn) | O(nlogn) | O(1) |
| 7 | 歸并排序 | 穩(wěn)定 | O(nlogn) | O(nlogn) | O(n) |
