經典排序演算法介紹

經典排序演算法介紹

來自專欄經典排序演算法

排序演算法可謂數據結構模塊中的重中之重，常見的哈希表，二叉樹，搜索樹/平衡樹，點陣圖等數據結構只是處理實際問題的抽象方法，實際在處理接受或生成的數據集時，排序演算法顯得尤其重要，排序演算法家族很龐大，其中包括了冒泡排序，選擇排序，插入排序，堆排序，快速排序，歸併排序，基數排序，計數排序，希爾排序，箱排序，樹型排序等眾多演算法，每種排序都有各自的特性，沒有好壞之分，只有在特定的場景使用合適的排序演算法才是上策，單純的來比顯得太過絕對，沒有可比性。因為實際需求及各方面條件的限制使得排序演算法的可選範圍往往只縮小到某一種或某幾種，所以要具體問題具體對待。

排序是計算機內經常進行的一種操作，其目的是將一組「無序」的記錄序列調整為「有序」的記錄序列。

排序分為內部排序和外部排序。

若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。

反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。

本文僅分析內部排序，故下面提到的排序演算法默認皆為內部排序演算法

十種常見排序演算法一般分為以下幾種：

（1）非線性時間比較類排序：通過比較來決定元素間的相對次序，由於其時間複雜度不能突破O(nlogn)，因此稱為非線性時間比較類排序。

（2）線性時間非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基於比較排序的時間下界，以線性時間運行，因此稱為線性時間非比較類排序。

總結：

（1）在比較類排序中，歸併排序號稱最快，其次是快速排序和堆排序，兩者不相伯仲，但是有一點需要注意，數據初始排序狀態對堆排序不會產生太大的影響，而快速排序卻恰恰相反。

（2）線性時間非比較類排序一般要優於非線性時間比較類排序，但前者對待排序元素的要求較為嚴格，比如計數排序要求待排序數的最大值不能太大，桶排序要求元素按照hash分桶後桶內元素的數量要均勻。線性時間非比較類排序的典型特點是以空間換時間。

演算法複雜度

相關概念

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。

不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。

時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。

空間複雜度：是指演算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。

參考資料：十大經典排序演算法（動圖演示） - 一像素 - 博客園

推薦閱讀：