戳藍字“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個同學小張和小趙年齡一樣的，本來舊隊伍的時候小張是排在小趙前面的，但是如果經過排序算法之後，把小張弄到了小趙的後面，這就不合理了，畢竟他們年齡一樣，肯定是剛開始誰在前面就保持原樣最好了，這就是體現出算法的穩定性的地方了。
對排序的穩定性要求是在實際應用中非常常見。
算法的複雜性：
算法本身的複雜度也會影響算法的性能（這裡不是指的時間空間複雜度），這裡指的算法設計思想的複雜度，後面我們在學習各種算法的時候就很清楚的看得到有的算法非常簡單，有的算法設計的就比較複雜了。像「冒泡排序」、「插入排序」、「選擇排序」這類都屬於簡單排序的算法。
以上，就是對數據結構中「 排序算法 」的一些思考。
閱讀更多 科技百分百 的文章
