前言
本文總結了常用的全部排序算法收厨，內容包括：
- 排序算法的定義和思路
- 排序算法的代碼實現(xiàn)：Python和Java渤弛，包括實現(xiàn)中需要注意的細節(jié)
- 排序算法性能分析：時間空間復雜度分析慨代，穩(wěn)定排序算法背誦口訣等
- 不同排序算法最佳使用場景
此文干貨頗多葬项，煩請收藏后慢慢研讀轻局。
-----正文開始-----
算法性能分析
圖中糾正：歸并排序空間復雜度應該是O(n)，快排是O(logn)-O(n)
穩(wěn)定性定義：
假定在待排序的記錄序列中挡毅，存在多個具有相同的關鍵字的記錄蒜撮，若經過排序，這些記錄的相對次序保持不變跪呈，即在原序列中段磨，r[i]=r[j]，且r[i]在r[j]之前耗绿，而在排序后的序列中苹支，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的缭乘；否則稱為不穩(wěn)定的沐序。
例如琉用，對于如下冒泡排序算法堕绩，原本是穩(wěn)定的排序算法，如果將記錄交換的條件改成r[j]>=r[j+1]邑时，則兩個相等的記錄就會交換位置奴紧，從而變成不穩(wěn)定的算法伊履。
再如用押，快速排序原本是不穩(wěn)定的排序方法，但若待排序記錄中只有一組具有相同關鍵碼的記錄彤路，而選擇的軸值恰好是這組相同關鍵碼中的一個浅浮，此時的快速排序就是穩(wěn)定的沫浆。
只需記住一句話（快些選一堆美女一起玩兒）是不穩(wěn)定的，其他都是穩(wěn)定的滚秩。
補充性能圖：
不同情況下的合適排序方法
初始數(shù)據(jù)越無序专执，快速排序越好。
已經基本有序時郁油，用直接插入排序最快本股。
在隨機情況下攀痊，快速排序是最佳選擇。
既要節(jié)省空間拄显，又要有較快的排序速度苟径，堆排序是最佳選擇，其不足之處是建堆時需要消耗較多時間躬审。
若希望排序是穩(wěn)定的棘街，且有較快的排序速度，則可選用2路歸并排序盒件，其缺點需要較大的輔助空間分配蹬碧。
算法實現(xiàn)
基于比較的排序算法
冒泡排序
思路：
冒泡排序的原理非常簡單，它重復地走訪過要排序的數(shù)列炒刁，一次比較兩個元素恩沽，如果他們的順序錯誤就把他們交換過來。
步驟：
- 比較相鄰的元素翔始。如果第一個比第二個大罗心，就交換他們兩個。
對第0個到第n-1個數(shù)據(jù)做同樣的工作城瞎。這時渤闷，最大的數(shù)就“浮”到了數(shù)組最后的位置上。 - 針對所有的元素重復以上的步驟脖镀，除了最后一個飒箭。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數(shù)字需要比較蜒灰。
Python:
def bubble_sort(array):
n = len(array)
for i in range(n): # i從0到n
for j in range(1, n-i): # 1開始弦蹂，即j-1=0開始
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
#優(yōu)化1：某一趟遍歷如果沒有數(shù)據(jù)交換，則說明已經排好序了强窖，因此不用再進行迭代了凸椿。
#用一個標記記錄這個狀態(tài)即可。
def bubble_sort2(ary):
n = len(ary)
for i in range(n):
flag = 1 #標記
for j in range(1,n-i):
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
flag = 0
if flag : #全排好序了翅溺，直接跳出
break
return ary
#優(yōu)化2：記錄某次遍歷時最后發(fā)生數(shù)據(jù)交換的位置脑漫，這個位置之后的數(shù)據(jù)顯然已經有序了。
# 因此通過記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了咙崎。
def bubble_sort3(ary):
n = len(ary)
k = n #k為循環(huán)的范圍优幸，初始值n
for i in range(n):
flag = 1
for j in range(1,k): #只遍歷到最后交換的位置即可
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
k = j #記錄最后交換的位置
flag = 0
if flag :
break
return ary
Java:
public void bubble_sort(int [] a) {
int n = a.length;
for(int i=0;i<n;i++) {
for(int j=1;j<n-i;j++) {
if (a[j-1] > a[j]) {
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
//兩種優(yōu)化不寫了
選擇排序
思路：
選擇排序無疑是最簡單直觀的排序。它的工作原理如下褪猛。
步驟：
- 在未排序序列中找到最型恕（大）元素，存放到排序序列的起始位置。
- 再從剩余未排序元素中繼續(xù)尋找最絮髓怠（大）元素严里，然后放到已排序序列的末尾。
- 以此類推追城，直到所有元素均排序完畢刹碾。
Python:
def selection_sort(array):
n = len(array)
for i in range(n):
minIndex = i
for j in range(i+1, n):
if array[j] < array[minIndex]:
minIndex = j
array[i], array[minIndex] = array[minIndex], array[i]
# 或者使用minNum存儲數(shù)值,避免每次都讀array[minIndex]，但如果每次都存儲新的minNum座柱，也會有損耗迷帜。
def selection_sort(array):
n = len(array)
for i in range(n):
minNum = array[i]
minIndex = i
for j in range(i+1, n):
if array[j] < minNum:
minIndex = j
minNum = array[j]
array[i], array[minIndex] = array[minIndex], array[i]
Java：
public void selection_sort(int [] a) {
int n = a.length;
for(int i=0;i<n;i++) {
int minIndex = i;
for(int j=i;j<n;j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
插入排序
思路：
從左邊第二個數(shù)開始，往前遍歷色洞，將大于他的數(shù)都往后一個個移位戏锹，一旦發(fā)現(xiàn)小于等于他的數(shù)，就放在那個位置（之前的數(shù)已經被移到后面一位了）
插入排序的工作原理是火诸，對于每個未排序數(shù)據(jù)锦针，在已排序序列中從后向前掃描，找到相應位置并插入置蜀。
步驟：
- 從第一個元素開始奈搜，該元素可以認為已經被排序
- 取出下一個元素，在已經排序的元素序列中從后向前掃描
- 如果被掃描的元素（已排序）大于新元素盯荤，將該元素后移一位
- 重復步驟3馋吗，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
Python：
def insert_sort(array):
n = len(array)
for i in range(1,n): # 從第二個數(shù)開始
if array[i-1] > array[i]: # 前面比后面大，需要調整位置
num = array[i]
index = i
for j in range(i-1, -1, -1):
if array[j] > num:
array[j+1] = array[j]
index = j
else: # 找到位置秋秤，插入
array[index] = num
break
Java：
public void insert_sort(int [] a) {
int n = a.length;
for(int i=1;i<n;i++) {
if (a[i-1] > a[i]) {
int num = a[i];
int index = i;
for(int j=i-1;j>-1;j--) {
if (a[j] > num) {
a[j+1] = a[j];
index = j;
}
else {
a[index] = num;
break;
}
}
}
}
}
希爾排序（遞減增量排序算法宏粤，實質是分組插入排序）
思路：
希爾排序的基本思想是：將數(shù)組列在一個表中并對列分別進行插入排序，重復這過程灼卢，不過每次用更長的列（步長更長了绍哎，列數(shù)更少了）來進行。最后整個表就只有一列了芥玉。將數(shù)組轉換至表是為了更好地理解這算法蛇摸，算法本身還是使用數(shù)組進行排序备图。
例如灿巧，假設有這樣一組數(shù)，
[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
如果我們以步長為5開始進行排序揽涮，我們可以通過將這列表放在有5列的表中來更好地描述算法抠藕，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數(shù)字，依序接在一起時我們得到：
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]
蒋困。這時10已經移至正確位置了盾似，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）。
具體實現(xiàn)：外面套一個gap，while內做插入排序零院，并且將gap不斷除2溉跃，直到小于0出循環(huán)
Python：
def shell_sort(ary):
n = len(ary)
gap = round(n/2) # 初始步長 , 用round取整(注意0.5向下取)
while gap > 0 :
for i in range(gap,n): # 每一列進行插入排序 , 從gap 到 n-1
temp = ary[i]
index = i
while ( index >= gap and ary[index-gap] > temp ): # 插入排序
ary[index] = ary[index-gap]
index = index - gap
ary[index] = temp
gap = round(gap/2) # 重新設置步長
return ary
Java：
public void shell_sort(int [] a) {
int n = a.length;
int gap = n / 2;
while (gap > 0) {
for (int i=gap;i<n;i++) {
int temp = a[i];
int j = i;
while (j>=gap && a[j-gap] > temp) {
a[j] = a[j-gap];
j = j - gap;
}
a[j] = temp;
}
gap = gap / 2;
}
}
歸并排序(遞歸合并)
思路：拆拆拆到單個數(shù)字，合并合并合并
歸并排序是采用分治法的一個非常典型的應用告抄。歸并排序的思想就是先遞歸分解數(shù)組撰茎，再合并數(shù)組。
先考慮合并兩個有序數(shù)組打洼，基本思路是比較兩個數(shù)組的最前面的數(shù)龄糊，誰小就先取誰，取了后相應的指針就往后移一位募疮。然后再比較炫惩，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復制過來即可阿浓。
再考慮遞歸分解他嚷，基本思路是將數(shù)組分解成left和right，如果這兩個數(shù)組內部數(shù)據(jù)是有序的芭毙，那么就可以用上面合并數(shù)組的方法將這兩個數(shù)組合并排序爸舒。如何讓這兩個數(shù)組內部是有序的？可以再二分稿蹲，直至分解出的小組只含有一個元素時為止扭勉，此時認為該小組內部已有序。然后合并排序相鄰二個小組即可苛聘。
Python：
def merge_sort(array): # 遞歸
if len(array) <= 1: return array # python每次都是新的數(shù)組涂炎，可以用數(shù)組長度小于等于1來判斷
num = len(array) // 2 # py27 3/2和3//2相同,python3 3//2才是地板除
left = merge_sort(array[:num])
right = merge_sort(array[num:])
return merge(left, right)
def merge(left, right): # 合并
l,r = 0,0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l = l + 1
else:
result.append(right[r])
r += 1
# 一邊沒有之后，加上所有的
result += left[l:]
result += right[r:]
return result
Java：
//注意：新建的temp長度和原數(shù)組是一樣的设哗，所以額外空間是O（n）唱捣，temp數(shù)組一開始并未賦值，在合并時慢慢給其填充數(shù)值网梢，所以說一共只有一個temp數(shù)組
public void mergeSort(int[] arr) {
mergeSort(arr, new int[arr.length], 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left < right) { // Java則通過左右指針來判斷
int center = (left + right) / 2;
mergeSort(arr, temp, left, center); // 左邊
mergeSort(arr, temp, center + 1, right); // 右邊
merge(arr, temp, left, center + 1, right); // 合并兩個有序
}
}
private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1; // 左邊結束下標
int tempPos = leftPos; // 從左邊開始算
int numEle = rightEnd - leftPos + 1; // 元素個數(shù)
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (arr[leftPos] <= arr[rightPos])
temp[tempPos++] = arr[leftPos++];
else
temp[tempPos++] = arr[rightPos++];
}
while (leftPos <= leftEnd) { // 左邊如果有剩余
temp[tempPos++] = arr[leftPos++];
}
while (rightPos <= rightEnd) { // 右邊如果有剩余
temp[tempPos++] = arr[rightPos++];
}
// 將temp復制到arr震缭，覆蓋原來這里的位置
for (int i = 0; i < numEle; i++) {
arr[rightEnd] = temp[rightEnd];
rightEnd--;
}
}
快速排序
快速排序通常明顯比同為Ο(n log n)的其他算法更快，因此常被采用战虏，而且快排采用了分治法的思想拣宰，所以在很多筆試面試中能經常看到快排的影子烦感⊙采纾可見掌握快排的重要性。
快排特點：
每經過一趟快排手趣，軸點元素都必然就位晌该，也就是說，一趟下來至少有關鍵字key節(jié)點在其最終位置，所以考察各個選項朝群，看有幾個元素就位即可燕耿。
逆序的數(shù)列，選擇首位為key姜胖，則會退化到O（n^2）缸棵，可以隨機選擇一個元素作為基準元素。
兩種交換方法：
- 指針交換法：youtube視頻：https://www.youtube.com/watch?v=gl_XQHTJ5hY （下圖代碼實現(xiàn)的方法谭期，并且是兩兩交換堵第，最后將key與left交換）
- 挖坑填數(shù)法：http://blog.csdn.net/morewindows/article/details/6684558 （key一開始就被挖坑填寫了別的數(shù)，我認為第二種是做潘沓觯客網選擇題時需要掌握的踏志，應為選擇題答案的排序結果通常是按照這種算法得到的排序結果）
快排優(yōu)化方法：
https://blog.csdn.net/cpcpcp123/article/details/52739285
選擇基準的方式：三數(shù)取中（median-of-three）
舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0
左邊為：8，右邊為0胀瞪，中間為6.
我們這里取三個數(shù)排序后针余，中間那個數(shù)作為樞軸，則樞軸為6
下圖分別對應第一種和第二種排序的中間結果：
Python(指針交換)：
def quick_sort(ary):
return _quick_sort(ary, 0, len(ary)-1)
def _quick_sort(ary, left, right):
if left >= right: return ary
key = ary[left] # 每次都選最左邊為key
lp = left
rp = right
while (lp < rp):
while ary[rp] >= key and lp < rp:
rp -= 1
while ary[lp] <= key and lp < rp:
lp += 1
ary[lp], ary[rp] = ary[rp], ary[lp]
ary[left], ary[lp] = ary[lp], ary[left] # 這里不能用key凄诞，是交換數(shù)組內數(shù)字
_quick_sort(ary, left, lp-1)
_quick_sort(ary, lp+1, right) # 這里lp, rp永遠是相等的圆雁。所以都可以。
return ary
Java(指針交換)：
public void quick_sort(int[] ary) {
_quick_sort(ary, 0, ary.length-1);
}
public void _quick_sort(int[] ary, int left, int right) {
if (left < right) {
int key = ary[left];
int lp = left;
int rp = right;
while (lp < rp) {
while (ary[rp] >= key && lp < rp ) {
rp--;
}
while (ary[lp] <= key && lp < rp ) {
lp++;
}
int temp = ary[lp];
ary[lp] = ary[rp];
ary[rp] = temp;
}
int temp = ary[lp];
ary[lp] = ary[left];
ary[left] = temp;
_quick_sort(ary, left, lp-1);
_quick_sort(ary, rp+1, right);
}
}
Java(挖坑法)
非遞歸形式實現(xiàn)（棧）：和剛才的遞歸實現(xiàn)相比帆谍，代碼的變動僅僅在quickSort方法當中伪朽。該方法中引入了一個存儲Map類型元素的棧，用于存儲每一次交換時的起始下標和結束下標汛蝙。
每一次循環(huán)烈涮，都會讓棧頂元素出棧，進行排序窖剑，并且按照基準元素的位置分成左右兩部分坚洽，左右兩部分再分別入棧。當棧為空時西土，說明排序已經完畢讶舰，退出循環(huán)。
該方法實現(xiàn)代碼請參考程序員小灰：
堆排序
參考：
http://blog.csdn.net/minxihou/article/details/51850001
https://www.2cto.com/kf/201609/549335.html
例題：相當幫助理解
https://www.nowcoder.com/test/question/done?tid=14276624&qid=56294#summary
思路：
父節(jié)點i的左子節(jié)點在位置(2i+1)*
父節(jié)點i的右子節(jié)點在位置(2i+2)*
子節(jié)點i的父節(jié)點在位置floor((i-1)/2)
堆排序構建堆的時間復雜度是N,而重調堆的時間復雜度是logN
堆可以分為大根堆和小根堆需了，這里用最大堆的情況來定義操作:
(1)最大堆調整(MAX_Heapify):
將堆的末端子節(jié)點作調整跳昼，使得子節(jié)點永遠小于父節(jié)點。這是核心步驟援所，在建堆和堆排序都會用到庐舟。比較i的根節(jié)點和與其所對應i的孩子節(jié)點的值欣除。當i根節(jié)點的值比左孩子節(jié)點的值要小的時候住拭，就把i根節(jié)點和左孩子節(jié)點所對應的值交換，當i根節(jié)點的值比右孩子的節(jié)點所對應的值要小的時候，就把i根節(jié)點和右孩子節(jié)點所對應的值交換滔岳。然后再調用堆調整這個過程杠娱，可見這是一個遞歸的過程。
(2)建立最大堆(Build_Max_Heap):
將堆所有數(shù)據(jù)重新排序谱煤。建堆的過程其實就是不斷做最大堆調整的過程摊求，從len/2出開始調整，一直比到第一個節(jié)點刘离。
(3)堆排序(HeapSort):
移除位在第一個數(shù)據(jù)的根節(jié)點室叉，并做最大堆調整的遞歸運算。堆排序是利用建堆和堆調整來進行的硫惕。首先先建堆茧痕，然后將堆的根節(jié)點選出與最后一個節(jié)點進行交換，然后將前面len-1個節(jié)點繼續(xù)做堆調整的過程恼除。直到將所有的節(jié)點取出踪旷，對于n個數(shù)我們只需要做n-1次操作。堆是用順序表存儲的的代碼可以先看：http://blog.51cto.com/ahalei/1427156 就能理解代碼中的操作
注意：
從小到大排序的時候不建立最小堆而建立最大堆豁辉。最大堆建立好后令野，最大的元素在h[ 1]。因為我們的需求是從小到大排序徽级，希望最大的放在最后气破。因此我們將h[ 1]和h[ n]交換，此時h[ n]就是數(shù)組中的最大的元素餐抢。
請注意堵幽，交換后還需將h[1]向下調整以保持堆的特性。OK現(xiàn)在最大的元素已經歸位弹澎，需要將堆的大小減1即n--朴下，然后再將h[1]和h[ n]交換，并將h[1]向下調整苦蒿。如此反復殴胧，直到堆的大小變成1為止。此時數(shù)組h中的數(shù)就已經是排序好的了佩迟。
代碼如下：
Python:
def MAX_Heapify(heap, HeapSize, root): # 在堆中做結構調整使得父節(jié)點的值大于子節(jié)點
left = 2 * root + 1
right = left + 1
larger = root
if left < HeapSize and heap[larger] < heap[left]:
larger = left
if right < HeapSize and heap[larger] < heap[right]: # 確定到底和左還是右節(jié)點換团滥，先判斷做節(jié)點
larger = right
if larger != root: # 如果做了堆調整：則larger的值等于左節(jié)點或者右節(jié)點的，這個時候做對調值操作
heap[larger],heap[root] = heap[root],heap[larger]
MAX_Heapify(heap, HeapSize, larger) # 從頂端遞歸往下調整报强，用larger是因為larger是數(shù)組索引灸姊，并且已經在比較時候更新過，而root沒有更新過秉溉！
def Build_MAX_Heap(heap): # 構造一個堆力惯，將堆中所有數(shù)據(jù)重新排序
HeapSize = len(heap)
for i in range(((HeapSize-1）-1)//2,-1,-1): # 從后往前出數(shù)(z最后一個節(jié)點的父節(jié)點) '//' got integer
MAX_Heapify(heap,HeapSize,i) # 這里堆的大小是固定碗誉，root是i逐步減小
def HeapSort(heap): # 將根節(jié)點取出與最后一位做對調，對前面len-1個節(jié)點繼續(xù)進行對調整過程父晶。
Build_MAX_Heap(heap)
for i in range(len(heap)-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
MAX_Heapify(heap, i, 0) # 這里堆的大小是逐步縮小哮缺，root永遠是0
return heap
Java：
有空補
非基于比較的排序算法
基于比較的排序算法是不能突破O(NlogN)的。簡單證明如下：
N個數(shù)有N!個可能的排列情況甲喝，也就是說基于比較的排序算法的判定樹有N!個葉子結點尝苇，比較次數(shù)至少為log(N!)=O(NlogN)(斯特林公式)。
計數(shù)排序
計數(shù)排序在輸入n個0到k之間的整數(shù)時(可以從a到b埠胖，不用非要從0開始糠溜，代碼可以實現(xiàn))，
時間復雜度最好情況下為O(n+k),最壞情況下為O(n+k),平均情況為O(n+k),空間復雜度為O(n+k)
算法的步驟如下：
1.找出待排序的數(shù)組中最大和最小的元素
2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)直撤，存入數(shù)組C的第i項
3.對所有的計數(shù)累加（從C中的第一個元素開始诵冒，每一項和前一項相加）
4.反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1
當k不是很大時谊惭，這是一個很有效的線性排序算法汽馋。更重要的是，它是一種穩(wěn)定排序算法圈盔，即排序后的相同值的元素原有的相對位置不會發(fā)生改變(表現(xiàn)在Order上)豹芯，這是計數(shù)排序很重要的一個性質，就是根據(jù)這個性質驱敲，我們才能把它應用到基數(shù)排序铁蹈。
# -*- coding:utf-8 -*-
def count_sort(ary):
max=min=0 # min和max應該用sys.maxint
for i in ary:
if i < min:
min = i
if i > max:
max = i
count = [0] * (max - min +1)
for index in ary:
count[index-min]+=1
index=0
for a in range(max-min+1):
for c in range(count[a]): # 重點：有多少個就for循環(huán)多少次
ary[index]=a+min
index+=1
return ary
桶排序
假如待排序列K= {49、 38 众眨、 35握牧、 97 、 76娩梨、 73 沿腰、 27、 49 }狈定。這些數(shù)據(jù)全部在1—100之間颂龙。因此我們定制10個桶，然后確定映射函數(shù)f(k)=k/10纽什。則第一個關鍵字49將定位到第4個桶中(49/10=4)措嵌。依次將所有關鍵字全部堆入桶中，并在每個非空的桶中進行快速排序芦缰。
因此企巢，我們需要盡量做到下面兩點：
(1) 映射函數(shù)f(k)能夠將N個數(shù)據(jù)平均的分配到M個桶中，這樣每個桶就有[N/M]個數(shù)據(jù)量让蕾。
(2) 盡量的增大桶的數(shù)量浪规。極限情況下每個桶只能得到一個數(shù)據(jù)或听，這樣就完全避開了桶內數(shù)據(jù)的“比較”排序操作。 當然罗丰，做到這一點很不容易神帅，數(shù)據(jù)量巨大的情況下再姑，f(k)函數(shù)會使得桶集合的數(shù)量巨大萌抵，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了元镀。
對于N個待排數(shù)據(jù)绍填，M個桶，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復雜度為：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
當N=M時栖疑，即極限情況下每個桶只有一個數(shù)據(jù)時讨永。桶排序的最好效率能夠達到O(N)。
桶排序是穩(wěn)定的遇革。
基數(shù)排序
基數(shù)排序的思想就是將待排數(shù)據(jù)中的每組關鍵字依次進行桶分配卿闹。比如下面的待排序列：
278、109萝快、063锻霎、930、589揪漩、184旋恼、505、269奄容、008冰更、083
我們將每個數(shù)值的個位，十位昂勒，百位分成三個關鍵字： 278 -> k1(個位)=8 蜀细，k2(十位)=7 ，k3=(百位)=2戈盈。
然后從最低位個位開始(從最次關鍵字開始)审葬，對所有數(shù)據(jù)的k1關鍵字進行桶分配(因為，每個數(shù)字都是 0-9的奕谭，因此桶大小為10)涣觉，再依次輸出桶中的數(shù)據(jù)得到下面的序列。
930血柳、063官册、083、184难捌、505膝宁、278鸦难、008、109员淫、589合蔽、269
再對上面的序列接著進行針對k2的桶分配，輸出序列為：
505介返、008拴事、109、930圣蝎、063刃宵、269、278徘公、083牲证、184、589
最后針對k3的桶分配关面，輸出序列為：
008坦袍、063、083等太、109捂齐、184、269澈驼、278辛燥、505、589缝其、930
很明顯挎塌，基數(shù)排序的性能比桶排序要略差。每一次關鍵字的桶分配都需要O(N)的時間復雜度内边，而且分配之后得到新的關鍵字序列又需要O(N)的時間復雜度榴都。假如待排數(shù)據(jù)可以分為d個關鍵字，則基數(shù)排序的時間復雜度將是O(d*2N) 漠其，當然d要遠遠小于N嘴高，因此基本上還是線性級別的『褪海基數(shù)排序的空間復雜度為O(N+M)拴驮，其中M為桶的數(shù)量。一般來說N>>M柴信，因此額外空間需要大概N個左右套啤。
但是，對比桶排序随常，基數(shù)排序每次需要的桶的數(shù)量并不多潜沦。而且基數(shù)排序幾乎不需要任何“比較”操作萄涯，而桶排序在桶相對較少的情況下，桶內多個數(shù)據(jù)必須進行基于比較操作的排序唆鸡。因此涝影，在實際應用中，基數(shù)排序的應用范圍更加廣泛争占。
參考
性能分析與適應場景：
http://blog.csdn.net/p10010/article/details/49557763
動畫：
http://blog.csdn.net/tobeandnottobe/article/details/7192953
http://www.webhek.com/post/comparison-sort.html
Python排序總結：
http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/
Java排序總結：
https://www.cnblogs.com/10158wsj/p/6782124.html?utm_source=tuicool&utm_medium=referral
