歡迎訪問(wèn)我的博客原文
??????鄭重聲明：轉(zhuǎn)載請(qǐng)務(wù)必注明出處！
排序算法是程序員必備的基礎(chǔ)知識(shí)预厌，弄明白它們的原理和實(shí)現(xiàn)很有必要阿迈。本文中將通過(guò)非常細(xì)節(jié)的動(dòng)畫(huà)展示出算法的原理，配合代碼更容易理解轧叽。
概述
由于待排序的元素?cái)?shù)量不同苗沧，使得排序過(guò)程中涉及的存儲(chǔ)器不同刊棕，可將排序方法分為兩類：一類是內(nèi)部排序，指的是待排序列存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程待逞；另一類是外部排序甥角，指的是待排序的元素的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄识樱，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程嗤无。
我們可以將常見(jiàn)的內(nèi)部排序算法可以分成兩類：
比較類排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，時(shí)間復(fù)雜度為 O(nlogn)～O(n2)怜庸。屬于比較類的有：
| 排序算法 | 時(shí)間復(fù)雜度 | 最差情況 | 最好情況 | 空間復(fù)雜度 | 排序方式 | 穩(wěn)定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1)? | In-place | ? |
| 快速排序 | O(nlogn)? | O(n2) | O(nlogn)? | O(logn)? | In-place | ? |
| 插入排序 | O(n2) | O(n2) | O(n)? | O(1)? | In-place | ? |
| 希爾排序 | O(nlog2n)? | O(n2) | O(n)? | O(1)? | In-place | ? |
| 選擇排序 | O(n2) | O(n2) | O(n2) | O(1)? | In-place | ? |
| 堆排序 | O(nlogn)? | O(nlogn) | O(nlogn)? | O(1)? | In-place | ? |
| 歸并排序 | O(nlogn)? | O(nlogn) | O(nlogn)? | O(n)? | Out-place | ? |
非比較類排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序当犯，其時(shí)間復(fù)雜度可以突破 O(nlogn)，以線性時(shí)間運(yùn)行割疾。屬于非比較類的有：
| 排序算法 | 時(shí)間復(fù)雜度 | 最差情況 | 最好情況 | 空間復(fù)雜度 | 排序方式 | 穩(wěn)定性 |
|---|---|---|---|---|---|---|
| 桶排序 | O(n+nlog(n/r))? | O(n2) | O(n)? | O(n+r)? | Out-place | ? |
| 計(jì)數(shù)排序 | O(n+r)? | O(n+r)? | O(n+r)? | O(n+r)? | Out-place | ? |
| 基數(shù)排序 | O(d(n+r))? | O(d(n+r)) | O(d(n+r)) | O(n+r)? | Out-place | ? |
名詞解釋：
時(shí)間/空間復(fù)雜度：描述一個(gè)算法執(zhí)行時(shí)間/占用空間與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系
n：待排序列的個(gè)數(shù)
r：“桶”的個(gè)數(shù)（上面的三種非比較類排序都是基于“桶”的思想實(shí)現(xiàn)的）
d：待排序列的最高位數(shù)
In-place：原地算法嚎卫，指的是占用常用內(nèi)存，不占用額外內(nèi)存宏榕⊥刂睿空間復(fù)雜度為 O(1) 的都可以認(rèn)為是原地算法
Out-place：非原地算法，占用額外內(nèi)存
穩(wěn)定性：假設(shè)待排序列中兩元素相等担扑，排序前后這兩個(gè)相等元素的相對(duì)位置不變恰响，則認(rèn)為是穩(wěn)定的。
冒泡排序
冒泡排序（Bubble Sort）涌献，顧名思義，就是指越小的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端首有。
算法原理
- 從左到右燕垃，依次比較相鄰的元素大小，更大的元素交換到右邊井联；
- 從第一組相鄰元素比較到最后一組相鄰元素卜壕，這一步結(jié)束最后一個(gè)元素必然是參與比較的元素中最大的元素；
- 按照大的居右原則烙常，重新從左到后比較轴捎，前一輪中得到的最后一個(gè)元素不參與比較，得出新一輪的最大元素蚕脏；
- 按照上述規(guī)則侦副，每一輪結(jié)束會(huì)減少一個(gè)元素參與比較，直到?jīng)]有任何一組元素需要比較驼鞭。
動(dòng)圖演示
代碼實(shí)現(xiàn)
void bubble_sort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j+1);
}
}
}
}
算法分析
冒泡排序?qū)儆?strong>交換排序秦驯，是穩(wěn)定排序，平均時(shí)間復(fù)雜度為 O(n2)挣棕，空間復(fù)雜度為 O(1)译隘。
但是我們城浊牛看到冒泡排序的最優(yōu)時(shí)間復(fù)雜度是 O(n)，那要如何優(yōu)化呢题篷？
我們可以用一個(gè) flag 參數(shù)記錄新一輪的排序中元素是否做過(guò)交換厅目，如果沒(méi)有，說(shuō)明前面參與比較過(guò)的元素已經(jīng)是正序璧瞬，那就沒(méi)必要再?gòu)念^比較了。代碼實(shí)現(xiàn)如下：
void bubble_sort_quicker(int arr[], int n) {
int i, j, flag;
for (i = 0; i < n - 1; i++) {
flag = 0;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j+1);
flag = 1;
}
}
if (!flag) return;
}
}
快速排序
快速排序（Quick Sort）渔欢，是冒泡排序的改進(jìn)版，之所以“快速”瘟忱，是因?yàn)槭褂昧?strong>分治法奥额。它也屬于交換排序垫挨，通過(guò)元素之間的位置交換來(lái)達(dá)到排序的目的九榔。
基本思想
在序列中隨機(jī)挑選一個(gè)元素作基準(zhǔn)涡相，將小于基準(zhǔn)的元素放在基準(zhǔn)之前催蝗，大于基準(zhǔn)的元素放在基準(zhǔn)之后丙号，再分別對(duì)小數(shù)區(qū)與大數(shù)區(qū)進(jìn)行排序犬缨。
一趟快速排序的具體做法是：
- 設(shè)兩個(gè)指針 i 和 j，分別指向序列的頭部和尾部截酷；
- 先從 j 所指的位置向前搜索迂苛，找到第一個(gè)比基準(zhǔn)小的值，把它與基準(zhǔn)交換位置就漾；
- 再?gòu)?i 所指的位置向后搜索抑堡，找到第一個(gè)比基準(zhǔn)大的值首妖，把它與基準(zhǔn)交換位置有缆；
- 重復(fù) 2棚壁、3 兩步栈虚，直到 i = j魂务。
仔細(xì)研究一下上述算法我們會(huì)發(fā)現(xiàn)头镊，在排序過(guò)程中相艇，對(duì)基準(zhǔn)的移動(dòng)其實(shí)是多余的坛芽，因?yàn)橹挥幸惶伺判蚪Y(jié)束時(shí)咙轩，也就是 i = j 的位置才是基準(zhǔn)的最終位置活喊。
由此可以優(yōu)化一下算法：
- 設(shè)兩個(gè)指針 i 和 j钾菊，分別指向序列的頭部和尾部煞烫；
- 先從 j 所指的位置向前搜索滞详，找到第一個(gè)比基準(zhǔn)小的數(shù)值后停下來(lái)料饥，再?gòu)?i 所指的位置向后搜索岸啡，找到第一個(gè)比基準(zhǔn)大的數(shù)值后停下來(lái)凰狞，把 i 和 j 指向的兩個(gè)值交換位置；
- 重復(fù)步驟2达布，直到 i = j，最后將相遇點(diǎn)指向的值與基準(zhǔn)交換位置产还。
動(dòng)圖演示
代碼實(shí)現(xiàn)
這里取序列的第一個(gè)元素為基準(zhǔn)脐区。
/* 選取序列的第一個(gè)元素作為基準(zhǔn) */
int select_pivot(int arr[], int low) {
return arr[low];
}
void quick_sort(int arr[], int low, int high) {
int i, j, pivot;
if (low >= high) return;
pivot = select_pivot(arr, low);
i = low;
j = high;
while (i != j) {
while (arr[j] >= pivot && i < j) j--;
while (arr[i] <= pivot && i < j) I++;
if (i < j) swap(arr, i, j);
}
arr[low] = arr[I];
arr[i] = pivot;
quick_sort(arr, low, i - 1);
quick_sort(arr, i + 1, high);
}
算法分析
快速排序是不穩(wěn)定排序牛隅，它的平均時(shí)間復(fù)雜度為 O(nlogn)媒佣，平均空間復(fù)雜度為 O(logn)默伍。
快速排序中也糊，基準(zhǔn)的選取非常重要显设，它將影響排序的效率捕捂。舉個(gè)例子指攒，假如序列本身順序隨機(jī)允悦，快速排序是所有同數(shù)量級(jí)時(shí)間復(fù)雜度的排序算法中平均性能最好的隙弛，但如果序列本身已經(jīng)有序或基本有序全闷，直接選取固定位置总珠，例如第一個(gè)元素作為基準(zhǔn)局服，會(huì)使快速排序就會(huì)淪為冒泡排序淫奔，時(shí)間復(fù)雜度為 O(n^2)唆迁。為了避免發(fā)生這種情況媒惕，引入下面兩種獲取基準(zhǔn)的方法：
隨機(jī)選取
就是選取序列中的任意一個(gè)數(shù)為基準(zhǔn)的值妒蔚。
/* 隨機(jī)選擇基準(zhǔn)的位置肴盏，區(qū)間在 low 和 high 之間 */
int select_pivot_random(int arr[], int low, int high) {
srand((unsigned)time(NULL));
int pivot = rand()%(high - low) + low;
swap(arr, pivot, low);
return arr[low];
}
三者取中
就是取起始位置菜皂、中間位置恍飘、末尾位置指向的元素章母，對(duì)這三個(gè)元素排序后取中間數(shù)作為基準(zhǔn)乳怎。
/* 取起始位置蚪缀、中間位置询枚、末尾位置指向的元素三者的中間值作為基準(zhǔn) */
int select_pivot_median_of_three(int arr[], int low, int high) {
// 計(jì)算數(shù)組中間的元素的下標(biāo)
int mid = low + ((high - low) >> 1);
// 排序哩盲，使 arr[mid] <= arr[low] <= arr[high]
if (arr[mid] > arr[high]) swap(arr, mid, high);
if (arr[low] > arr[high]) swap(arr, low, high);
if (arr[mid] > arr[low]) swap(arr, low, mid);
// 使用 low 位置的元素作為基準(zhǔn)
return arr[low];
}
經(jīng)驗(yàn)證明廉油，三者取中的規(guī)則可以大大改善快速排序在最壞情況下的性能班巩。
插入排序
直接插入排序（Straight Insertion Sort）抱慌，是一種簡(jiǎn)單直觀的排序算法抑进，它的基本操作是不斷地將尚未排好序的數(shù)插入到已經(jīng)排好序的部分寺渗，好比打撲克牌時(shí)一張張抓牌的動(dòng)作信殊。在冒泡排序中涡拘，經(jīng)過(guò)每一輪的排序處理后鳄乏，序列后端的數(shù)是排好序的汞窗；而對(duì)于插入排序來(lái)說(shuō)不铆，經(jīng)過(guò)每一輪的排序處理后誓斥，序列前端的數(shù)都是排好序的劳坑。
基本思想
先將第一個(gè)元素視為一個(gè)有序子序列距芬，然后從第二個(gè)元素起逐個(gè)進(jìn)行插入框仔，直至整個(gè)序列變成元素非遞減有序序列為止离斩。如果待插入的元素與有序序列中的某個(gè)元素相等跛梗，則將待插入元素插入大相等元素的后面。整個(gè)排序過(guò)程進(jìn)行 n-1 趟插入宪祥。
動(dòng)圖演示
代碼實(shí)現(xiàn)
void insertion_sort(int arr[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = arr[i];
for (j = i; j > 0 && arr[j - 1] > temp; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}
算法分析
插入排序是穩(wěn)定排序，平均時(shí)間復(fù)雜度為 O(n2)耀找，空間復(fù)雜度為 O(1)野芒。
希爾排序
希爾排序（Shell's Sort）是第一個(gè)突破 O(n2) 的排序算法狞悲，是直接插入排序的改進(jìn)版摇锋，又稱“縮小增量排序”（Diminishing Increment Sort）。它與直接插入排序不同之處在于融求，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素生宛。
基本思想
先將整個(gè)待排序列分割成若干個(gè)字序列分別進(jìn)行直接插入排序陷舅，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序缩赛。
子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”酥馍，將相隔某個(gè)增量的記錄組成一個(gè)子序列旨袒，讓增量逐趟縮短砚尽，直到增量為 1 為止猾骡。
動(dòng)圖演示
代碼實(shí)現(xiàn)
增量序列可以有各種取法兴想，例如上面動(dòng)圖所示，增量序列滿足 [n / 2, n / 2 / 2, ..., 1]毙替，n 是序列本身的長(zhǎng)度蔚龙，這也是一種比較流行的增量序列定義方式木羹。這時(shí)希爾排序的算法可以通過(guò)下面的代碼實(shí)現(xiàn)：
void shell_sort_split_half(int arr[], int n) {
int i, j, dk, temp;
for (dk = n >> 1; dk > 0; dk = dk >> 1) {
for (i = dk; i < n; i++) {
temp = arr[i];
for (j = i - dk; j >= 0 && arr[j] > temp; j -= dk)
arr[j + dk] = arr[j];
arr[j + dk] = temp;
}
}
}
增量序列也可以有其它的定義方式，那么希爾排序的實(shí)現(xiàn)可以歸納成這樣：
void shell_insert(int arr[], int n, int dk) {
int i, j, temp;
for (i = dk; i < n; i += dk) {
temp = arr[i];
j = i - dk;
while (j >= 0 && temp < arr[j]) {
arr[j + dk] = arr[j];
j -= dk;
}
arr[j + dk] = temp;
}
}
void shell_sort(int arr[], int n, int dlta[], int t) {
int k;
for (k = 0; k < t; ++k) {
// 一趟增量為 dlta[k] 的插入排序
shell_insert(arr, n, dlta[k]);
}
}
算法分析
希爾排序是不穩(wěn)定排序脐瑰，它的分析是一個(gè)復(fù)雜的問(wèn)題，因?yàn)樗倪\(yùn)行時(shí)間依賴于增量序列的選擇寂恬，它的平均時(shí)間復(fù)雜度為O(n^1.3)初肉，最好情況是 O(n)臼隔，最差情況是 O(n2)摔握『蟹ⅲ空間復(fù)雜度為 O(1)拼卵。
選擇排序
選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法腋腮。它的基本思想就是即寡，每一趟 n-i+1(i=1,2,...,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列的第 i 個(gè)記錄莺丑。
算法步驟
簡(jiǎn)單選擇排序：
- 在未排序序列中找到最猩颐А（大）元素昏名，存放到排序序列的起始位置;
- 在剩余未排序元素中繼續(xù)尋找最星峋帧（大）元素，放到已排序序列的末尾;
- 重復(fù)步驟2样刷，直到所有元素排序完畢仑扑。
動(dòng)圖演示
代碼實(shí)現(xiàn)
void selection_sort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
int min = I;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min])
min = j;
}
swap(arr, min, i);
}
}
算法分析
選擇排序是不穩(wěn)定排序，時(shí)間復(fù)雜度固定為 O(n2)颂斜，因此它不適用于數(shù)據(jù)規(guī)模較大的序列夫壁。不過(guò)它也有優(yōu)點(diǎn)沃疮，就是不占用額外的內(nèi)存空間盒让。
堆排序
堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法梅肤。堆的特點(diǎn)：
- 一顆完全二叉樹(shù)（也就是會(huì)所生成節(jié)點(diǎn)的順序是：從上往下、從左往右）
- 每一個(gè)節(jié)點(diǎn)必須滿足父節(jié)點(diǎn)的值不大于/不小于子節(jié)點(diǎn)的值
基本思想
實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題：
如何將一個(gè)無(wú)序序列構(gòu)建成堆邑茄？
如何在輸出堆頂元素后姨蝴，調(diào)整剩余元素成為一個(gè)新的堆？
以升序?yàn)槔温疲惴▽?shí)現(xiàn)的思路為：
- 建立一個(gè)
build_heap函數(shù)左医，將數(shù)組 tree[0,...n-1] 建立成堆，n 表示數(shù)組長(zhǎng)度同木。函數(shù)里需要維護(hù)的是所有節(jié)點(diǎn)的父節(jié)點(diǎn)浮梢，最后一個(gè)子節(jié)點(diǎn)下標(biāo)為 n-1，那么它對(duì)應(yīng)的父節(jié)點(diǎn)下標(biāo)就是(n-1-1)/2彤路。 - 構(gòu)建完一次堆后秕硝，最大元素就會(huì)被存放在根節(jié)點(diǎn) tree[0]。將 tree[0] 與最后一個(gè)元素交換洲尊，每一輪通過(guò)這種不斷將最大元素后移的方式远豺，來(lái)實(shí)現(xiàn)排序。
- 而交換后新的根節(jié)點(diǎn)可能不滿足堆的特點(diǎn)了坞嘀，因此需要一個(gè)調(diào)整函數(shù) heapify 來(lái)對(duì)剩余的數(shù)組元素進(jìn)行最大堆性質(zhì)的維護(hù)躯护。如果 tree[i] 表示其中的某個(gè)節(jié)點(diǎn)，那么 tree[2*i+1] 是左孩子丽涩，tree[2*i+2] 是右孩子棺滞，選出三者中的最大元素的下標(biāo)，存放于 max 值中内狸，若 max 不等于 i检眯，則將最大元素交換到 i 下標(biāo)的位置。但是昆淡，此時(shí)以 tree[max] 為根節(jié)點(diǎn)的子樹(shù)可能不滿足堆的性質(zhì)锰瘸，需要遞歸調(diào)用自身。
動(dòng)圖演示
代碼實(shí)現(xiàn)
void heapify(int tree[], int n, int i) {
// n 表示序列長(zhǎng)度昂灵，i 表示父節(jié)點(diǎn)下標(biāo)
if (i >= n) return;
// 左側(cè)子節(jié)點(diǎn)下標(biāo)
int left = 2 * i + 1;
// 右側(cè)子節(jié)點(diǎn)下標(biāo)
int right = 2 * i + 2;
int max = I;
if (left < n && tree[left] > tree[max]) max = left;
if (right < n && tree[right] > tree[max]) max = right;
if (max != i) {
swap(tree, max, i);
heapify(tree, n, max);
}
}
void build_heap(int tree[], int n) {
// 樹(shù)最后一個(gè)節(jié)點(diǎn)的下標(biāo)
int last_node = n - 1;
// 最后一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)下標(biāo)
int parent = (last_node - 1) / 2;
int I;
for (i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
void heap_sort(int tree[], int n) {
build_heap(tree, n);
int I;
for (i = n - 1; i >= 0; i--) {
// 將堆頂元素與最后一個(gè)元素交換
swap(tree, i, 0);
// 調(diào)整成大頂堆
heapify(tree, i, 0);
}
}
算法分析
堆排序是不穩(wěn)定排序避凝，適合數(shù)據(jù)量較大的序列，它的平均時(shí)間復(fù)雜度為 Ο(nlogn)眨补，空間復(fù)雜度為 O(1)管削。
此外，堆排序僅需一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間撑螺。
歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種排序算法含思。它和快速排序一樣，采用了分治法。
基本思想
歸并的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表含潘。也就是說(shuō)饲做，從幾個(gè)數(shù)據(jù)段中逐個(gè)選出最小的元素移入新數(shù)據(jù)段的末尾，使之有序遏弱。
那么歸并排序的算法我們可以這樣理解：
假如初始序列含有 n 個(gè)記錄盆均，則可以看成是 n 個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為 1漱逸。然后兩兩歸并泪姨，得到 n/2 個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并饰抒，……肮砾，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為 n 的有序序列為止袋坑，這種排序方法稱為 二路歸并排序唇敞，下文介紹的也是這種排序方式。
動(dòng)圖演示
代碼實(shí)現(xiàn)
/* 將 arr[L..M] 和 arr[M+1..R] 歸并 */
void merge(int arr[], int L, int M, int R) {
int LEFT_SIZE = M - L + 1;
int RIGHT_SIZE = R - M;
int left[LEFT_SIZE];
int right[RIGHT_SIZE];
int i, j, k;
// 以 M 為分割線咒彤，把原數(shù)組分成左右子數(shù)組
for (i = L; i <= M; i++) left[i - L] = arr[i];
for (i = M + 1; i <= R; i++) right[i - M - 1] = arr[i];
// 再合并成一個(gè)有序數(shù)組（從兩個(gè)序列中選出最小值依次插入）
i = 0; j = 0; k = L;
while (i < LEFT_SIZE && j < RIGHT_SIZE) arr[k++] = left[i] < right[j] ? left[i++] : right[j++];
while (i < LEFT_SIZE) arr[k++] = left[i++];
while (j < RIGHT_SIZE) arr[k++] = right[j++];
}
void merge_sort(int arr[], int L, int R) {
if (L == R) return;
// 將 arr[L..R] 平分為 arr[L..M] 和 arr[M+1..R]
int M = (L + R) / 2;
// 分別遞歸地將子序列排序?yàn)橛行驍?shù)列
merge_sort(arr, L, M);
merge_sort(arr, M + 1, R);
// 將兩個(gè)排序后的子序列再歸并到 arr
merge(arr, L, M, R);
}
算法分析
歸并排序是穩(wěn)定排序，它和選擇排序一樣咒精，性能不受輸入數(shù)據(jù)的影響镶柱，但表現(xiàn)比選擇排序更好，它的時(shí)間復(fù)雜度始終為 O(nlogn)模叙，但它需要額外的內(nèi)存空間歇拆，空間復(fù)雜度為 O(n)。
桶排序
桶排序（Bucket sort）是計(jì)數(shù)排序的升級(jí)版范咨。它利用了函數(shù)的映射關(guān)系故觅，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
桶排序的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布渠啊，將數(shù)據(jù)分到有限數(shù)量的桶里输吏，每個(gè)桶再分別排序（也有可能是使用別的排序算法或是以遞歸方式繼續(xù)用桶排序進(jìn)行排序）。
算法步驟
- 設(shè)置固定數(shù)量的空桶替蛉；
- 把數(shù)據(jù)放在對(duì)應(yīng)的桶內(nèi)贯溅；
- 分別對(duì)每個(gè)非空桶內(nèi)數(shù)據(jù)進(jìn)行排序；
- 拼接非空的桶內(nèi)數(shù)據(jù)躲查，得到最終的結(jié)果它浅。
動(dòng)圖演示
代碼實(shí)現(xiàn)
void bucket_sort(int arr[], int n, int r) {
if (arr == NULL || r < 1) return;
// 根據(jù)最大/最小元素和桶數(shù)量，計(jì)算出每個(gè)桶對(duì)應(yīng)的元素范圍
int max = arr[0], min = arr[0];
int i, j;
for (i = 1; i < n; i++) {
if (max < arr[i]) max = arr[I];
if (min > arr[i]) min = arr[I];
}
int range = (max - min + 1) / r + 1;
// 建立桶對(duì)應(yīng)的二維數(shù)組镣煮，一個(gè)桶里最多可能出現(xiàn) n 個(gè)元素
int buckets[r][n];
memset(buckets, 0, sizeof(buckets));
int counts[r];
memset(counts, 0, sizeof(counts));
for (i = 0; i < n; i++) {
int k = (arr[i] - min) / range;
buckets[k][counts[k]++] = arr[I];
}
int index = 0;
for (i = 0; i < r; i++) {
// 分別對(duì)每個(gè)非空桶內(nèi)數(shù)據(jù)進(jìn)行排序姐霍，比如計(jì)數(shù)排序
if (counts[i] == 0) continue;
counting_sort(buckets[i], counts[I]);
// 拼接非空的桶內(nèi)數(shù)據(jù)，得到最終的結(jié)果
for (j = 0; j < counts[i]; j++) {
arr[index++] = buckets[i][j];
}
}
}
算法分析
桶排序是穩(wěn)定排序，但僅限于桶排序本身镊折，假如桶內(nèi)排序采用了快速排序之類的非穩(wěn)定排序胯府，那么就是不穩(wěn)定的。
時(shí)間復(fù)雜度
桶排序的時(shí)間復(fù)雜度可以這樣看：
- n 次循環(huán)腌乡，每個(gè)數(shù)據(jù)裝入桶
- r 次循環(huán)盟劫，每個(gè)桶中的數(shù)據(jù)進(jìn)行排序（每個(gè)桶中平均有 n/r 個(gè)數(shù)據(jù)）
假如桶內(nèi)排序用的是選擇排序這類時(shí)間復(fù)雜度較高的排序，整個(gè)桶排序的時(shí)間復(fù)雜度就是 O(n)+O(n2)与纽，視作 O(n2)侣签，這是最差的情況；
假如桶內(nèi)排序用的是比較先進(jìn)的排序算法急迂，時(shí)間復(fù)雜度為 O(nlogn)影所，那么整個(gè)桶排序的時(shí)間復(fù)雜度為 O(n)+O(r*(n/r)*log(n/r))=O(n+nlog(n/r))。k=nlog(n/r)僚碎，桶排序的平均時(shí)間復(fù)雜度為 O(n+k)猴娩。當(dāng) r 接近于 n 時(shí)，k 趨近于 0勺阐，這時(shí)桶排序的時(shí)間復(fù)雜度是最優(yōu)的卷中，就可以認(rèn)為是 O(n)。也就是說(shuō)如果數(shù)據(jù)被分配到同一個(gè)桶中渊抽，排序效率最低蟆豫；但如果數(shù)據(jù)可以均勻分配到每一個(gè)桶中，時(shí)間效率最高懒闷，可以線性時(shí)間運(yùn)行十减。但同樣地，桶越多愤估，空間就越大帮辟。
空間復(fù)雜度
占用額外內(nèi)存，需要?jiǎng)?chuàng)建 r 個(gè)桶的額外空間玩焰，以及 n 個(gè)元素的額外空間由驹，所以桶排序的空間復(fù)雜度為 O(n+r)。
計(jì)數(shù)排序
計(jì)數(shù)排序（Counting Sort）是一種非比較性質(zhì)的排序算法震捣，利用了桶的思想荔棉。它的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的輔助空間中，也就是說(shuō)這個(gè)輔助空間的長(zhǎng)度取決于待排序列中的數(shù)據(jù)范圍蒿赢。
如何轉(zhuǎn)化成桶思想來(lái)理解呢润樱？我們?cè)O(shè)立 r 個(gè)桶，桶的鍵值分別對(duì)應(yīng)從序列最小值升序到最大值的所有數(shù)值羡棵。接著壹若，按照鍵值，依次把元素放進(jìn)對(duì)應(yīng)的桶中，然后統(tǒng)計(jì)出每個(gè)桶中分別有多少元素店展，再通過(guò)對(duì)桶內(nèi)數(shù)據(jù)的計(jì)算养篓，即可確定每一個(gè)元素最終的位置。
算法步驟
- 找出待排序列中最大值 max 和最小值 min赂蕴，算出序列的數(shù)據(jù)范圍 r = max - min + 1柳弄，申請(qǐng)輔助空間 C[r]；
- 遍歷待排序列概说，統(tǒng)計(jì)序列中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)碧注，記錄在輔助空間的第 i 位；
- 對(duì)輔助空間內(nèi)的數(shù)據(jù)進(jìn)行計(jì)算（從空間中的第一個(gè)元素開(kāi)始萍丐，每一項(xiàng)和前一項(xiàng)相加），以確定值為 i 的元素在數(shù)組中出現(xiàn)的位置放典；
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在目標(biāo)數(shù)組的第 C[i] 位奋构，每放一個(gè)元素就將 C[i] 減1态贤，直到 C 中所有值都是 0
動(dòng)圖演示
代碼實(shí)現(xiàn)
void counting_sort(int arr[], int n) {
if (arr == NULL) return;
// 定義輔助空間并初始化
int max = arr[0], min = arr[0];
int I;
for (i = 1; i < n; i++) {
if (max < arr[i]) max = arr[I];
if (min > arr[i]) min = arr[I];
}
int r = max - min + 1;
int C[r];
memset(C, 0, sizeof(C));
// 定義目標(biāo)數(shù)組
int R[n];
// 統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)
for (i = 0; i < n; i++) C[arr[i] - min]++;
// 對(duì)輔助空間內(nèi)數(shù)據(jù)進(jìn)行計(jì)算
for (i = 1; i < r; i++) C[i] += C[i - 1];
// 反向填充目標(biāo)數(shù)組
for (i = n - 1; i >= 0; i--) R[--C[arr[i] - min]] = arr[i];
// 目標(biāo)數(shù)組里的結(jié)果重新賦值給 arr
for (i = 0; i < n; i++) arr[i] = R[i];
}
算法分析
計(jì)數(shù)排序?qū)儆?strong>非交換排序芥驳，是穩(wěn)定排序，適合數(shù)據(jù)范圍不顯著大于數(shù)據(jù)數(shù)量的序列茬高。
時(shí)間復(fù)雜度
它的時(shí)間復(fù)雜度是線性的兆旬，為 O(n+r)，r 表示待排序列中的數(shù)據(jù)范圍怎栽，也就是桶的個(gè)數(shù)丽猬。可以這樣理解：將 n 個(gè)數(shù)據(jù)依次放進(jìn)對(duì)應(yīng)的桶中熏瞄，再?gòu)?r 個(gè)桶中把數(shù)據(jù)按順序取出來(lái)脚祟。
空間復(fù)雜度
占用額外內(nèi)存，還需要 r 個(gè)桶强饮，因此空間復(fù)雜度是 O(n+r)由桌，計(jì)數(shù)排序快于任何比較排序算法，但這是通過(guò)犧牲空間換取時(shí)間來(lái)實(shí)現(xiàn)的。
基數(shù)排序
基數(shù)排序（Radix Sort）是非比較型排序算法行您，它和計(jì)數(shù)排序铭乾、桶排序一樣，利用了“桶”的概念娃循】婚荩基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字間的比較，是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法捌斧。比如數(shù)字100笛质，它的個(gè)位、十位骤星、百位就是不同的關(guān)鍵字经瓷。
那么，對(duì)于一組亂序的數(shù)字洞难，基數(shù)排序的實(shí)現(xiàn)原理就是將整數(shù)按位數(shù)（關(guān)鍵字）切割成不同的數(shù)字舆吮，然后按每個(gè)位數(shù)分別比較。對(duì)于關(guān)鍵字的選擇队贱，有最高位優(yōu)先法（MSD法）和最低位優(yōu)先法（LSD法）兩種方式色冀。MSD 必須將序列先逐層分割成若干子序列，然后再對(duì)各子序列進(jìn)行排序柱嫌；而 LSD 進(jìn)行排序時(shí)锋恬，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序编丘。
算法步驟
以 LSD 法為例：
- 將所有待比較數(shù)值（非負(fù)整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度与学，數(shù)位不足的數(shù)值前面補(bǔ)零
- 從最低位（個(gè)位）開(kāi)始，依次進(jìn)行一次排序
- 從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列
如果要支持負(fù)數(shù)參加排序嘉抓，可以將序列中所有的值加上一個(gè)常數(shù)索守，使這些值都成為非負(fù)數(shù)，排好序后抑片，所有的值再減去這個(gè)常數(shù)卵佛。
動(dòng)圖演示
代碼實(shí)現(xiàn)
// 基數(shù)，范圍0~9
#define RADIX 10
void radix_sort(int arr[], int n) {
// 獲取最大值和最小值
int max = arr[0], min = arr[0];
int i, j, l;
for (i = 1; i < n; i++) {
if (max < arr[i]) max = arr[I];
if (min > arr[i]) min = arr[I];
}
// 假如序列中有負(fù)數(shù)敞斋，所有數(shù)加上一個(gè)常數(shù)截汪，使序列中所有值變成正數(shù)
if (min < 0) {
for (i = 0; i < n; i++) arr[i] -= min;
max -= min;
}
// 獲取最大值位數(shù)
int d = 0;
while (max > 0) {
max /= RADIX;
d ++;
}
int queue[RADIX][n];
memset(queue, 0, sizeof(queue));
int count[RADIX] = {0};
for (i = 0; i < d; i++) {
// 分配數(shù)據(jù)
for (j = 0; j < n; j++) {
int key = arr[j] % (int)pow(RADIX, i + 1) / (int)pow(RADIX, i);
queue[key][count[key]++] = arr[j];
}
// 收集數(shù)據(jù)
int c = 0;
for (j = 0; j < RADIX; j++) {
for (l = 0; l < count[j]; l++) {
arr[c++] = queue[j][l];
queue[j][l] = 0;
}
count[j] = 0;
}
}
// 假如序列中有負(fù)數(shù)，收集排序結(jié)果時(shí)再減去前面加上的常數(shù)
if (min < 0) {
for (i = 0; i < n; i++) arr[i] += min;
}
}
算法分析
基數(shù)排序是穩(wěn)定排序植捎，適用于關(guān)鍵字取值范圍固定的排序衙解。
時(shí)間復(fù)雜度
基數(shù)排序可以看作是若干次“分配”和“收集”的過(guò)程。假設(shè)給定 n 個(gè)數(shù)焰枢，它的最高位數(shù)是 d丢郊，基數(shù)（也就是桶的個(gè)數(shù)）為 r盔沫，那么可以這樣理解：共進(jìn)行 d 趟排序，每趟排序都要對(duì) n 個(gè)數(shù)據(jù)進(jìn)行分配枫匾，再?gòu)?r 個(gè)桶中收集回來(lái)架诞。所以算法的時(shí)間復(fù)雜度為 O(d(n+r))，在整數(shù)的排序中干茉，r = 10谴忧，因此可以簡(jiǎn)化成 O(dn)，是線性階的排序角虫。
空間復(fù)雜度
占用額外內(nèi)存沾谓，需要?jiǎng)?chuàng)建 r 個(gè)桶的額外空間，以及 n 個(gè)元素的額外空間戳鹅，所以基數(shù)排序的空間復(fù)雜度為 O(n+r)均驶。
計(jì)數(shù)排序 & 桶排序 & 基數(shù)排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
- 桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值枫虏，適用于元素盡可能分布均勻的排序妇穴；
- 計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值阎曹，適用于最大值和最小值盡可能接近的排序岳锁；
- 基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶腐魂，適用于非負(fù)整數(shù)間的排序蛾娶，且最大值和最小值盡可能接近。
本文關(guān)聯(lián)項(xiàng)目地址
