排序算法至關重要，它和查找算法一塊兒做爲整個算法體系的基石算法
對用例來講，處理一組有序數據總要比處理一組無序數據容易得多。數組
好比要在數組中查找特定元素，若是數組是總體有序的，查找會很是輕鬆(經典的二分查找算法就要求數據集的是總體有序的，其運行的平均時間複雜度僅爲 O(log n))，否則用例恐怕只得遍歷一遍數組了！數據結構
自人類步入信息時代， 近幾十年來，生產的信息已超過過去5000年的總和。而信息經過數據存儲和傳輸。如此巨量的數據若是不通過有序性的組織，而全以雜亂無章存在，那必然會大大增長人類社會的複雜性，讓處理不少問題變得不可能。有了以前聊到的諸多排序算法存在，才得以讓人類社會以更加簡單的方式運行。搜索引擎
有強迫症的同窗會很是樂於將物品按照某種順序組織好，以便後續取用；字典中將文字按照字母順序印刷，再結合編撰好的索引，咱們就能快速從中找到待查文字；搜索引擎返回的結果將網頁按照與關鍵詞的相關程度排序；Windows 系統的資源管理器、各類花名冊，甚至於咱們參加集體活動時須要列隊都是按照身高排列……排序
排序的應用是如此普遍，結合計算機，排序算法又是如此的重要！有序性總會使待解決的問題更容易解決，因此排序常常做爲待解決問題的一個子問題存在。想象一下，對比雜亂無序的一組數據，你是否是更樂於處理整潔有序的一組數據？索引
前面七篇文章咱們依次聊了——冒泡排序、選擇排序、插入排序、希爾排序、堆排序、歸併排序和快速排序這幾種主要的排序算法，來列張表對比總結下：資源
| 排序算法 | 穩定性 | 原地排序 | 時間複雜度 | 空間複雜度 | 補充說明 |
|---|---|---|---|---|---|
| 冒泡排序 | Y | Y | 平均 O(n^2) | O(1) | 最簡單的排序算法 |
| 選擇排序 | N | Y | 平均 O(n^2) | O(1) | 運行時間輸入無關 |
| 插入排序 | Y | Y | 平均 O(n^2) | O(1) | 運行時間嚴重依賴輸入，待排序數組若是已經總體有序，則只需線性級別的時間複雜度 |
| 希爾排序 | N | Y | 最壞 О(n log²n)；最佳O(n) | O(1) | 改進版插入排序 |
| 堆排序 | N | Y | 恆爲 O(n log n) | O(1) | 依賴於二叉堆這種數據結構 |
| 歸併排序 | Y | N | 恆爲 O(n log n) | O(n) | 應用普遍，須要額外輔助空間 |
| 快速排序 | N | Y | 平均 O(n log n) | 依賴於具體實現 | 應用最普遍的排序算法，運行效率由機率保證 |
排序算法的穩定性是指算法是否會保持數組中鍵值相同元素的相對順序不變。table
快速排序是當下最快的通用排序算法。效率
如上所述，排序算法至關重要，它和查找算法一塊兒做爲整個算法體系的基石。OK下篇文章，咱們開始聊查找~搜索
完。