基于比較的排序：

　　基礎排序：

　　　　 ?冒泡排序：誰大誰上，每一輪都把最大的頂到天花板 效率太低——掌握swap。

　　　　選擇排序：效率較低，但經常用它內部的循環方式來找最大值和最小值。

　　　　插入排序：雖然平均效率低，但是在序列基本有序時，它很快，所以也有其適用范圍。

　　　　希爾排序（縮小增量排序）：是插排的改良，對空間思維訓練有幫助 時間復雜度O(n^1.3)，介于O(nlgn)~O(n²)之間

　　分治法：

　　　　快速排序：是軟件工業中最常見的常規排序法，其雙向指針掃描和分區算法是核心，特別地partition算法用來劃分不同性質的元素，如選擇第K大元素的問題。快速排序時間復雜度為O(NlgN)，但是如果主元不是中位數的話，特別地如果每次主元都在數組區間的一側，復雜度將退化為N2，工業上的優化方法見快速排序分區以及優化方法。快速排序重視子問題的劃分。

　　　　歸并排序：分治法的完美使用，開辟了輔助空間，常見的題目如逆序對數，歸并排序重視子問題的解的合并

　　　　堆排序：用到了二叉堆數據結構，是繼續掌握樹結構的起手式 堆排序 ?= 插排 + 二分查找

　　　　上面三個都是NlgN的復雜度，其中快排表現最好，是原址的不用開辟輔助空間；歸并排序需要開辟輔助空間；堆排也是原址的，但是常數因子較大，不具備優勢。

基于非比較排序：

　　計數排序：可以說是最快的，用它來解決問題時必須注意如果序列中的值分布非常廣（最大值很大，元素分布很稀疏），那么空間將會浪費很多，所以計數排序的使用范圍是：序列的關鍵字比較集中，已知邊界，且邊界較小。

　　桶排序：用它解決問題必須注意序列的值是否均勻地分布在桶中。如果不均勻，那么個別桶中的元素會遠多于其他桶，桶內排序用比較排序，極端情況下，全部元素在一個桶內，那么復雜度還是會退化成NlgN。

　　基數排序：kN級別（k是最大數的位數）是整數數值型排序里面又快又穩的，無論元素分布如何，只開辟固定的輔助空間（10個桶），基數排序幾乎不需要任何“比較”操作。因此，在實際應用中，對十進制整數來說，基數排序更好用。

　　上面三種排序其實都是支持負數的，我們可以找出最小的數來，計算出與0的距離，然后把所有的數同時減去這個距離，這樣就全部成為自然數，排好序然后再恢復回去就OK了。

十種排序算法對比：

　　

?

轉載于:https://www.cnblogs.com/xiaoyh/p/10286280.html

總結

以上是生活随笔為你收集整理的10种排序算法基础总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。