戳藍字“CSDN云計算”關注我們哦！作者 |??奎哥責編 | 阿禿
之前的文章咱們已經聊過了
下圖是常用排序算法的時間空間復雜度：排序算法這么多，這里先將排序算法做個簡單分類：

一、可以根據待排序的數據量規模分類：

• 內部排序：在排序過程中，待排序的數據能夠被全部加載進內存中
• 外部排序：待排序的數據太大，不能全部同時放入內存，排序過程中需要內存與外部存儲交換數據

二、可以根據排序的穩定性進行分類：

• 穩定性排序：冒泡排序、插入排序、歸并排序
• 不穩定排序：快速排序、選擇排序、希爾排序、堆排序

三、可以根據排序時間復雜度分類：

• O(N)：桶排序、計數排序、基數排序
• O(NlogN)：快速排序、希爾排序、歸并排序、堆排序
• O(N*N)：冒泡排序、插入排序、選擇排序

四、基于算法思想分類：

• 基于分治：快速排序、歸并排序
• 基于插入：希爾排序、插入排序
• 基于選擇：堆排序、選擇排序
• 基于交換：冒泡排序、快速排序

這些分類其實并沒有那么嚴格，大多都是根據排序算法的特性總結的，不需要記住，搞懂了各種排序的特點之后也就自然而然的理解了。這么多排序算法，我們應該怎么去評估它們呢？一般而言，評估一個排序算法的質量主要從以下幾個角度去看：

• 時間復雜度：這是衡量算法性能的常規方法，對于排序算法當然也不例外，這也是衡量排序算法最重要的一個指標。在排序算法中常用的操作就是“比較”和“移動”元素，因此我們想優化某個排序算法的時間復雜度就是要減少去“比較”和“移動”元素的次數。同時，由于需排序的數據不同會導致即使同一個算法也有著完全不同的時間消耗，因此我們還應該進一步分析排序算法的 最好時間復雜度、最壞時間復雜度，以及平均時間復雜度，以做到對排序算法特性的充分了解。
• 空間復雜度：這個也是評價算法的另一個常規指標。需要分析執行算法所需要的輔助存儲空間（原有數據已占用的空間不算）。如果空間復雜度為O(1)則說明執行算法的輔助存儲空間為常量級別，很優秀。對于「冒泡排序」、「插入排序」、「選擇排序」等排序算法的空間復雜度都是O(1)。
• 排序的穩定性：排序的穩定性是一個新的指標，對于排序算法來說非常的重要。通俗的來講就是：假如在待排序的數組中有相等的元素，則經過排序之后，這些相等的元素之間的原有順序不被改變。例如：待排序數組：1，3，6，5，6，2，9，經過從小到大的排序之后為：1，2，3，5，6，6，9在原數組里面有2個6，分別位于數組的第二個位置和第四個位置（數組從第0位開始數），在排序后這2個6分為位于數組的第四個位置和第五個位置。注意重點來了，穩定性要求就是指原來那個第二位置的6是在第四個位置的6的前面的，所以排序完成之后，這兩個6的相對向后順序不能有變，因此位于新數組第四個位置的6必須是原來舊數組的第二個位置的那個6，新數組第五個位置的6必須是舊數組時第四個位置的那個6，雖然值一樣，但是還是有區別的。你要說有啥區別？那再舉個例子吧：幼兒園一群小孩排隊去領零食，剛開始是雜亂無章的排隊的，后來老師說按照年齡大小排隊，年齡小的排到前面去，這個時候就可以運用排序算法進行年齡的排序了。可是隊伍中有2個同學小張和小趙年齡一樣的，本來舊隊伍的時候小張是排在小趙前面的，但是如果經過排序算法之后，把小張弄到了小趙的后面，這就不合理了，畢竟他們年齡一樣，肯定是剛開始誰在前面就保持原樣最好了，這就是體現出算法的穩定性的地方了。對排序的穩定性要求是在實際應用中非常常見。
• 算法的復雜性：算法本身的復雜度也會影響算法的性能（這里不是指的時間空間復雜度），這里指的算法設計思想的復雜度，后面我們在學習各種算法的時候就很清楚的看得到有的算法非常簡單，有的算法設計的就比較復雜了。像「冒泡排序」、「插入排序」、「選擇排序」這類都屬于簡單排序的算法。

以上，就是對數據結構中「 排序算法 」的一些思考。


福利
掃描添加小編微信，備注“姓名+公司職位”，入駐【CSDN博客】，加入【云計算學習交流群】，和志同道合的朋友們共同打卡學習！

推薦閱讀：

• 
  

• 
  
  

真香，朕在看了！ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的看完秒懂的排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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