線性時間排序
對于比較排序來說沃琅，在排序的最終結(jié)果中哗咆，各元素的次序依賴于它們之間的比較。我們可以看到下圖中的比較排序算法益眉，在最壞情況下情況下晌柬，時間復雜度至少O(nlgn)。
從圖中我們可以較為清楚的看到各算法的時間復雜度郭脂，下面將證明對包含n個元素的輸入序列來說年碘，在最壞情況下，時間復雜度至少都是O(nlgn)展鸡。
比較排序可以被抽象為一顆決策樹屿衅，那什么是決策樹呢？比如上圖所示莹弊，現(xiàn)在要出去相親涤久，首先判斷年齡，如果大于30歲忍弛，那就直接不見了响迂，小于30再考慮其他條件。之后细疚，我們依次判斷了蔗彤，長相，收入惠昔，都滿足了要求幕与，于是決定去見上一面。
決策樹是一顆完全二叉樹（美式定義：要么有左右孩子镇防、要么就沒有孩子）啦鸣，非葉子結(jié)點都是一個邏輯判斷，每個分支都是判斷結(jié)果来氧。
如上圖所示诫给，現(xiàn)在有三個數(shù)x,y,z香拉。我們可以構(gòu)建出如圖所示的決策樹，根結(jié)點是x和y比較中狂，如果x≤y凫碌，再比較y和z的大小，如果x≥y胃榕，則比較x和z的大小盛险。這里有三個數(shù)，并且是互異的勋又，所以大小排列情況會有6種苦掘，如果有n個互譯的數(shù)，那就是n!種楔壤。當x=6鹤啡，y=8，z=5時蹲嚣，最后就會得到<z,x,y>這個結(jié)果递瑰，也就是<5,6,8>。
在最壞情況下隙畜，比較的次數(shù)抖部，就是樹的高度，2的h次方表示的是禾蚕，總共的結(jié)點您朽，肯定比葉子結(jié)點多，最后可以解出换淆，h是大于等于O(nlgn)的哗总。
介紹完了比較排序的時間復雜度，現(xiàn)在該介紹線性時間排序了倍试。
計數(shù)排序
問題描述：給定一個無序的序列讯屈，對序列進行排序，使之成為有序县习。
基本思想：對于每一個輸入元素x涮母，確定小于x的元素個數(shù)，可以直接把x放到它在輸出數(shù)組中的位置上,但是需要略微修改躁愿，因為一個位置不能存放兩個元素
算法的主要思想就是找到比元素x小的元素個數(shù)叛本，元素x是待排序的元素。
那這個排序過程如何實現(xiàn)的呢彤钟？
A數(shù)組就是我們的待排序序列{2来候，5，3逸雹，0营搅，2云挟，3，0转质，3}园欣，C數(shù)組是用來記錄比元素x小的元素個數(shù)，因為A中的數(shù)是0-5休蟹，所以B中的數(shù)組大小也是0~5沸枯，上標表示的就是A中的數(shù)。
我們現(xiàn)在先記錄鸡挠，每個元素的個數(shù)是多少辉饱，現(xiàn)在指向2所以2的個數(shù)標記為1。
指向5拣展，所以5的個數(shù)變?yōu)?。
在完成后缔逛，數(shù)組C中記錄下了备埃，各元素的個數(shù)。不過我們最終要的結(jié)果是記錄下比元素x小的元素個數(shù)褐奴，所以這里面的數(shù)字還要進行簡單的變換按脚。
現(xiàn)在我們將1中的0變更為2，這個數(shù)字表示的是小于等于1的數(shù)敦冬，也就是2辅搬，下面我們再記錄小于等于2的數(shù)。
小于等于2的個數(shù)脖旱，就是前面小于等于1的個數(shù)堪遂，再加上2自身的個數(shù)，結(jié)果為4萌庆。
在完成更新后溶褪，所得如上圖所示，每個數(shù)組中記錄的數(shù)践险，就是小于等于自身的元素的個數(shù)猿妈。
B數(shù)組就是我們最后的排序結(jié)果，對A數(shù)組從右向左進行遍歷巍虫，這樣是為了讓排序是穩(wěn)定的彭则，排序的穩(wěn)定是指，對于相同的數(shù)字占遥，比如這里的2俯抖，在排序完成后，并不改變它們的相對次序筷频。
這里我們對3進行排序蚌成，去B數(shù)組查找前痘，小于等于3的個數(shù)，找到為7就直接放在上標為7的數(shù)組中担忧，并且將B中記錄的數(shù)字減1芹缔。
排序完成的結(jié)果，如圖所示瓶盛。
因為要遍歷兩遍A數(shù)組最欠，以及遍歷一遍B數(shù)組，所以時間復雜度為O(n)+O(n)+O(k)=O(k+n)惩猫，當k=O(n)時T(n)=O(n)芝硬。
基數(shù)排序
基本思想：基數(shù)排序的總體思路就是將待排序數(shù)據(jù)拆分成多個關鍵字進行排序，實質(zhì)是多關鍵字排序轧房。
注意事項：選擇低位優(yōu)先排序拌阴，因為如果按照高位優(yōu)先排序的，當排到次高位時奶镶，還需要返回看高位數(shù)字,相對來說比較麻煩迟赃。
例如，現(xiàn)在給出了7個數(shù)字厂镇，我們要對其進行排序纤壁，在這種位數(shù)很多的情況下，我們優(yōu)先選擇的就是基數(shù)排序捺信。在基數(shù)排序時酌媒，優(yōu)先對個位數(shù)進行排序，也就是最右邊的那位數(shù)迄靠。
要對個位數(shù)數(shù)字進行排序秒咨，那選擇什么樣的方法對其進行排序呢？只要是線性時間的排序梨水，都是可行的拭荤，這里我們選擇之前講過的計數(shù)排序。
再對十位數(shù)上面的數(shù)字進行排序疫诽。
在完成排序后舅世，可以得到上圖的結(jié)果。
時間復雜度分析：
每個數(shù)字都是d位數(shù)奇徒，比如說這里都是三位數(shù)雏亚。每一次排序，都是計數(shù)排序摩钙，時間復雜度為O(n+k)罢低，總共d次計數(shù)排序。所以時間復雜度為O(n+k)d=O(d(n+k))。
桶排序
一般來說网持，只有在輸入數(shù)據(jù)是給定的一個范圍內(nèi)宜岛，并且還是服從均勻分布的，才會使用桶排序功舀。
A中就是給出的數(shù)據(jù)萍倡，這些數(shù)據(jù)都是0到1之間的數(shù)，B中就是我們準備的10個桶辟汰，數(shù)字0到9表示的是數(shù)據(jù)小數(shù)點后一位的數(shù)列敲。
開始進行排序，第一個數(shù)字是0.78帖汞，所以放在了7號桶里面戴而。
當進行到0.72時依然是放到7號桶里面，不過要和0.78比較一下大小翩蘸，然后進行排序所意。
最后的排序結(jié)果，如圖所示鹿鳖。
