相信閱讀過前面5篇博文的童鞋們已經發現了“在排序的最終結果中，各元素的次序依賴于它們之間的比較”。于是乎，這類排序算法被統稱為”比較排序“。
比較排序是通過一個單一且抽象的比較運算（比如“小于等于”）讀取清單元素，而這個比較運算則決定了每兩個元素中哪一個應該先出現在最終的排序清單中。
聲明：下面通過在維基百科中找到的非常完美的圖示來介紹一系列比較排序。
在該系列的【算法】1中我們便介紹了這個基本的算法，它的比較過程如下：
以下是用插入排序對30個元素的數組進行排序的動畫：
選擇排序的比較過程如下：
其動畫效果如下：
前面多次寫到歸并排序，它的比較過程如下：
歸并排序的動畫如下：
在該系列的【算法】4中我們便介紹了快排，建構堆的過程如下：
堆排序的動畫如下：
在該系列的【算法】5中我們便介紹了快排，它的比較過程如下：
快速排序的動畫如下：
以下這些排序同樣也是比較排序，但該系列中之前并未提到。
該算法是一種混合排序算法，開始于快速排序，當遞歸深度超過基于正在排序的元素數目的水準時便切換到堆排序。它包含了這兩種算法優良的部分，它實際的性能相當于在典型資料集上的快速排序和在最壞情況下的堆排序。由于它使用了兩種比較排序，因而它也是一種比較排序。
大家應該多少都聽過冒泡排序（也被稱為下沉排序），它是一個非常基本的排序算法。反複地比較相鄰的兩個元素并适當的互換它們，如果清單中已經沒有元素需要互換則表示該清單已經排好序了。（看到清單就想到半年前在學的scheme，歡迎大家也去看看，我開了2個專欄來介紹它們）
上面的描述中已經展現了比較的過程，因而冒泡排序也是一個比較排序，較小的元素被稱為“泡（bubble）”，它将“浮”到清單的頂端。
盡管這個算法非常簡單，但大家應該也聽說了，它真的非常的慢。
冒泡排序的過程如下：
冒泡排序的動畫示範：
其最好情況、最壞情況的運作時間分别是：Θ(n)、Θ(n2)。
奇偶排序和冒泡排序有很多類似的特點，它通過比較在清單中所有的單雙号索引的相鄰元素，如果有一對是錯誤排序（也就是前者比後者大），那麼将它們交換，之後不斷的重複這一步驟，直到整個清單排好序。
而鑒于此，它的最好情況、最壞情況的運作時間均和冒泡排序相同：Θ(n)、Θ(n2)。
奇偶排序的示範如下：
下面是c++中奇偶排序的示例：
雙向冒泡排序也被稱為雞尾酒排序、雞尾酒調酒器排序、搖床排序、漣漪排序、洗牌排序、班車排序等。（再多再華麗麗的名字也難以彌補它的低效）
和冒泡排序的差別在于它是在兩個方向上周遊清單進行排序，雖然如此但并不能提高漸近性能，和插入排序比起來也沒太多優勢。
它的最好情況、最壞情況的運作時間均和冒泡排序相同：Θ(n)、Θ(n2)。
我們可以将排序操作進行得多塊？
這取決于計算模型，模型簡單來說就是那些你被允許的操作。
決策樹（decision tree）是一棵完全二叉樹，它可以表示在給定輸入規模情況下，其一特定排序算法對所有元素的比較操作。其中的控制、資料移動等其他操作都被忽略了。
這是一棵作用于3個元素時的插入排序的決策樹。标記為i:j的内部結點表示ai和aj之間的比較。
由于它作用于3個元素，是以共有a33=6種可能的排列。也正是以，它并不具有一般性。
而對序列<a1=7,a2=2,a3=5>和序列<a1=5,a2=9,a3=6>進行排序時所做的決策已經由灰色和黑色粗箭頭指出了。
如果決策樹是針對n個元素排序，那麼它的高度至少是nlgn。
在最壞情況下，任何比較排序算法都需要做Ω(nlgn)次比較。
因為輸入資料的ann種可能的排列都是葉結點，是以ann≤l，由于在一棵高位h的二叉樹中，葉結點的數目不多于2h，是以有：
n!≤l≤2h
對兩邊取對數：
=> lg2h≥lgn!
=> lg2h=hlg2≥lgn!
又因為：
lg2<1
是以：
n≥lgn!=Ω(nlgn)
因為堆排序和歸并排序的運作時間上界均為o(nlgn)，是以它們都是漸近最優的比較排序算法。
計數排序（counting sort）的思路很簡單，就是确定比x小的數有多少個。加入有10個，那麼x就排在第11位。
嚴謹來講，在計算機科學中，計數排序是一個根據比較鍵值大小的排序算法，它也是一個整數排序算法。它通過比較對象的數值來操作，并通過這些計數來确定它們在即将輸出的序列中的位置。它的運作時間是線性的且取決于最大值和最小值之間的差異，當值的變化明顯大于數目時就不太适用了。而它也可以作為基排序的子程式。
第2-3步，c數組的元素被全部初始化為0，此時耗費Θ(k)時間。
第4-5步，也許不太好想象，其實就是在c數組中來計數a數組中的數。比如說，a數組中元素”3”有4個，那麼c[3]=4。此時耗費Θ(n)時間。
第7-8步，也是不太好想象的計算，也就是說如果c[0]=1、c[1]=4，那麼計算後的c[0]不變，c[1]=5。此時耗費Θ(k)時間。
第10-12步，把每個元素a[j]放到它在輸出數組b中的合适位置。比如此時的第一次循環，先找到a[8]，然後找到c[a[8]]的值，此時c[a[8]]的意義就在于a[8]應在b數組中的位置。完成這一步後将c[a[8]]的值減一，因為它隻是一個計數器。這裡耗費的時間為Θ(n)。
當k=o(n)時，計數排序的運作時間為Θ(n)。
基數排序（radix sort）是一個古老的算法，它用于卡片排序機上。說來也巧，寫這篇部落格的前一天晚上還在書上看到這種機器，它有80列，每一列都有12個孔可以打。
它可以使用前面介紹的計數排序作為子程式，然而它并不是原址排序；相比之下，很多運作時間為Θ(nlgn)的比較排序卻是原址排序。是以當資料過大而記憶體不太夠時，使用它并不是一個明智的選擇。
關鍵在于依次對從右往左每一列數進行排序，其他的列也相應移動。
這倒是一個有趣的算法了，它充分利用了連結清單的思想。
桶排序（bucket sort）在平均情況下的運作時間為o(n)。
計數排序假設n個輸入元素中的每一個都在0和k之間，桶排序假設輸入資料是均勻分布的，是以他們的速度都非常快。但并不能因為這些是假設就說它們不實用不準确，真正的意義在于你可以根據情況選擇合适的算法。比如說，輸入的n個元素并不是均勻分布的，但它們都在0到k之間，那麼就可以用計數排序。
說到桶，我想到的是裝滿葡萄酒的酒桶以及裝滿火藥的火藥桶。這裡是桶是指的算法将[0,1)區域劃分為了n個相同大小的空間，它們被稱為桶。
既然有了這個劃分，那麼就要用到它們。假設輸入的是n個元素的數組a，且對于所有的i都有0≤a[i]<1。你也許會覺得怎麼可能輸入的數組元素都湊巧滿足呢，當然不會這麼湊巧，但是你可以人為地改造它們呀。比如<10,37,31,87>，你可以将它們都除以100，得到<0.10,0.37,0.31,0.87>。
還需要一個臨時的數組b[0…n-1]來儲存這些桶（也就是連結清單），而連結清單支援搜尋，删除和插入。關于連結清單的部分後面的部落格中會有詳細介紹。
學習算法一定要體會到這種算法内每一步的改變，也要體會不同算法之間的演化和進步。在後面的連結清單中，我會更加側重于思路以及算法的進化。
感謝您的通路，希望對您有所幫助。 歡迎大家關注、收藏以及評論。
為使本文得到斧正和提問，轉載請注明出處：
http://blog.csdn.net/nomasp