寫(xiě)在前面
個(gè)人感覺(jué)：javascript對(duì)類似排序查找這樣的功能已經(jīng)有了很好的封裝，以致于當(dāng)我們想對(duì)數(shù)組排序的時(shí)候只需要調(diào)用
arr.sort()方法，而查找數(shù)組元素也只需要調(diào)用indexOf()方法或lastIndexOf()方法，我們忽略了其內(nèi)部的實(shí)現(xiàn)。而今，js能開(kāi)發(fā)的項(xiàng)目越來(lái)越龐大，對(duì)性能和效率要求也越來(lái)越高，雖然眾多的庫(kù)和框架也可以幫我們應(yīng)付這些問(wèn)題，但小編覺(jué)得框架過(guò)眼云煙，把握程序開(kāi)發(fā)的基礎(chǔ)，才能在飛速的更新?lián)Q代中應(yīng)對(duì)自如。因此我們不妨也研究一下這些算法，其中的思路有助于我們自身的提高。
聲明：本文章中的部分圖片來(lái)自百度搜索，如侵刪。
冒泡排序
這個(gè)是最簡(jiǎn)單的排序，就像氣泡從水里冒出來(lái)。
它每執(zhí)行一次外層循環(huán)，就會(huì)將最小數(shù)（或最大的）放到數(shù)組最后，然后再尋找剩余部分的最小數(shù)（或最大的）放在這一部分的最后，以此類推。
每一個(gè)外層循環(huán)的過(guò)程可以用一下圖來(lái)描述：
冒泡排序的時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 穩(wěn)定 排序。適用于數(shù)據(jù)比較少或基本有序的情況。
//冒泡排序
bubbleSort = function(arr){
var len = arr.length;
for (var i = 0; i < len; i++){
for (var j = 0; j < len - i - 1; j++){
if (arr[j] > arr[j + 1])
[arr[j + 1], arr[j]] = [arr[j],arr[j + 1]];
}
}
}
選擇排序
選擇排序也很簡(jiǎn)單。它每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。下面是完整的選擇排序過(guò)程：
選擇排序的時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 穩(wěn)定 排序。適用于數(shù)據(jù)比較少的情況，綜合各種情況來(lái)講還是這個(gè)最慢。
//選擇排序
selectionSort = function(arr){
var len = arr.length;
var min, min_index;//min每次找到的最小值，min_index最小值在無(wú)序序列的位置
for (var i = 0; i < len - 1; i++){
min = arr[i];
for (var j = i + 1; j < len; j++){//找到最小值
if (arr[j] < min){
min = arr[j];//找到的最小值
min_index = j;//找到的最小值索引
}
}
if (min != arr[i])
[arr[min_index], arr[i]] = [arr[i], arr[min_index]];
}
}
插入排序
這個(gè)要略微復(fù)雜一點(diǎn)了。它的思路就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，依然保持有序。實(shí)現(xiàn)過(guò)程把數(shù)組看作2部分，一部分是有序的，一部分是無(wú)序的，每次大循環(huán)將無(wú)序數(shù)組的第一個(gè)元素插入到有序的數(shù)組中。
插入排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 穩(wěn)定 排序。算法適用于少量數(shù)據(jù)的排序。
<small>注：二分插入和直接插入各種情況復(fù)雜度一樣</small>
//直接插入排序
insertionSort = function (arr){
var len = arr.length;
var temp;//temp每次要執(zhí)行插入的值
var index;//index插入值在有序序列的位置
for (var i = 1; i < len; i++){
temp = arr[i];
for (var j = 0; j < i; j++){//找到插入位置
index = i;
if (arr[j] > temp){
index = j;//找到的插入點(diǎn)索引
break;
}
}
if (i != index){
for (var j = i; j > index; j--)//插入該值
[arr[j - 1], arr[j]] = [arr[j],arr[j - 1]];
}
arr[index] = temp;
}
}
快速排序
這個(gè)想必大家都耳熟能詳，20世紀(jì)十大經(jīng)典算法之一。主要原因還是它極大的推動(dòng)了信息技術(shù)的發(fā)展，可惜它不是穩(wěn)定算法。
這個(gè)算法比較就比較難理解了，它通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的任一數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。這里面包含的分治的思想。
下面一個(gè)圖表現(xiàn)了函數(shù)的一次執(zhí)行過(guò)程：
而這個(gè)圖表現(xiàn)了整個(gè)排序過(guò)程：
快速排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 不穩(wěn)定 排序。
////快速排序(前軸）
function quickSort(arr){
qSort(0, arr.length - 1);
return arr;
function qSort(left, right){
if (left >= right)//兩個(gè)數(shù)相遇則結(jié)束該輪排序
return;
var key = arr[left];//取最左邊的元素作為標(biāo)識(shí)數(shù)
var i = left;
var j = right;
while (i != j){//兩個(gè)數(shù)相遇則結(jié)束該輪排序
while (i != j && arr[j] >= key) j--;//j前移
[arr[j], arr[i]] = [arr[i], arr[j]];
while (i != j && arr[i] <= key) i++;//i后移
[arr[j], arr[i]] = [arr[i], arr[j]];
}
qSort(left, j - 1);//對(duì)標(biāo)識(shí)數(shù)前面的數(shù)繼續(xù)該方法排序
qSort(j + 1, right);//對(duì)標(biāo)識(shí)數(shù)后面的數(shù)繼續(xù)該方法排序
}
}
這里補(bǔ)充一下：快速排序由于其實(shí)軸的選擇不同，分為前軸、中軸、后軸快速排序，上面的例子是前軸快速排序，下文比較算法的時(shí)候也才用上述代碼。不過(guò)，這里補(bǔ)充另外2種代碼：
//中軸快速排序
quickSortM: function(arr){
qSort(arr, 0, arr.length - 1);
return arr;
function qSort(arr, left, right){
if (left < right){
var index = Math.floor((left + right) / 2);
var key = arr[index];
var i = left - 1;
var j = right + 1;
while (true){
while (arr[++i] < key); // 向右找大于軸的數(shù)
while (arr[--j] > key); // 向左找小于軸的數(shù)
if (i >= j)//兩索引相同結(jié)束排序
break;
[arr[i], arr[j]] = [arr[j],arr[i]];//交換找到的數(shù)
}
qSort(arr, left, i - 1); // 繼續(xù)這樣對(duì)軸前面的排序
qSort(arr, j + 1, right); // 繼續(xù)這樣對(duì)軸后面的排序
}
}
}
//后軸快速排序
function quickSortB(arr){
qSort(0, arr.length - 1);
return arr;
function qSort(left, right){
if (left >= right)//兩索引相同結(jié)束排序
return;
var key = arr[right];
var i = left - 1;//s是最右邊的軸
for (var j = left; j < right; j++){ //將數(shù)據(jù)分成大于軸和小于軸兩部分
if (arr[j] <= key){
i++;
[arr[i], arr[j]] = [arr[j],arr[i]];
}
}
i++;
[arr[right], arr[i]] = [arr[i],arr[right]];//將軸插入到大于軸和小于軸兩部分的中間
qSort(left, i - 1);//繼續(xù)這樣對(duì)軸前面的排序
qSort(i, right);//繼續(xù)這樣對(duì)軸后面的排序
}
}
歸并排序
這個(gè)排序在小編眼里用的是最廣泛的，很多函數(shù)封裝內(nèi)部都才用這個(gè)排序，包括數(shù)據(jù)庫(kù)在內(nèi)的排序也采用了歸并排序或紅黑樹(shù)的形式。這個(gè)排序也用到了分治的思想：它將一個(gè)序列逐級(jí)拆分成小序列，將小序列排序后合并，得到完全有序的序列。若每次將序列分成2個(gè)子序列，再依此合并，稱為二路歸并。
沒(méi)理解？看圖：
歸并排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 穩(wěn)定 排序。
//歸并排序
mergeSort = function(arr){
var temp = [];
merge(arr, 0, arr.length - 1, temp);
return arr;
function merge(arr, left, right, temp){//temp是臨時(shí)空間，存放排序過(guò)程中間結(jié)果
var mid;//該部分中間位置
if (left >= right)//分組小于等于1時(shí)歸并結(jié)束
return;
mid = Math.floor((left + right) / 2);
merge(arr, left, mid, temp);//對(duì)中間位置之前部分繼續(xù)該方法排序
merge(arr, mid + 1, right, temp);//對(duì)中間位置之后部分繼續(xù)該方法排序
var i = left, j = mid + 1, k = left;
while (i != mid + 1 && j != right + 1)//比較兩部分每個(gè)值，把較小的放入temp中，并后移該指針，直到某部分全部遍歷
temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
//將未全部遍歷部分?jǐn)?shù)據(jù)順次放入temp中
while (i != mid + 1)
temp[k++] = arr[i++];
while (j != right + 1)
temp[k++] = arr[j++];
//將temp復(fù)制會(huì)a中
for (i = left; i <= right; i++)
arr[i] = temp[i];
}
}
希爾排序
這是惟一一個(gè)用人名命名的排序算法。它把數(shù)據(jù)按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
這個(gè)估計(jì)最不好理解了，看看圖吧：
希爾排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 不穩(wěn)定 排序。
//希爾排序
shellSort = function(arr){
var len = arr.length;
var index = Math.floor(len / 2);//得到比較步長(zhǎng)
var j, temp;
while (index > 0){
for (var i = index; i < len; i++){//遍歷起點(diǎn)后移，保證每個(gè)數(shù)在該步長(zhǎng)下參與且只參與1此排序
temp = arr[i];
for (j = i; j >= index && arr[j - index] > temp;){//等步長(zhǎng)數(shù)列執(zhí)行插入排序
arr[j] = arr[j - index];
j -= index;
arr[j] = temp;
}
}
index = Math.floor(index / 2);//步長(zhǎng)減半
}
}
堆排序
首先說(shuō)一下一個(gè)名詞：大根堆。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即， 屬于完全二叉樹(shù)。
根據(jù)大根堆的要求可知，最大的值一定在堆頂，根據(jù)其特點(diǎn)，如果要求每個(gè)節(jié)點(diǎn)的左孩子小于右孩子，得到的就是數(shù)據(jù)從小到大的排列。反之從大到小排列應(yīng)該使用小根堆。
如果你對(duì)二叉樹(shù)熟悉的話，可以簡(jiǎn)單用圖理解一下
堆排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 不穩(wěn)定 排序。
下面利用數(shù)組快速定位指定索引的元素模擬堆操作，并沒(méi)有實(shí)際建立二叉樹(shù)。
//堆排序
heapSort = function(arr){
var len = arr.length;
for (var i = len / 2 - 1; i >= 0; i--)//反向遍歷數(shù)組，將數(shù)組調(diào)整為大根堆
heapAdjust(arr, i, len);
for (var i = len - 1; i > 0; i--){
[arr[0], arr[i]] = [arr[i], arr[0]];//將無(wú)需部分最大數(shù)放在最后，即構(gòu)成有序部分
heapAdjust(arr, 0, i);//將剩余無(wú)需部分調(diào)整為大根堆，直到該部分只有一個(gè)元素為止
}
return arr;
function heapAdjust(arr, i, len){//二叉堆調(diào)整函數(shù)，負(fù)責(zé)將堆調(diào)整成大根堆（因?yàn)槭窃鲂蚺帕校? var child;//根孩子的索引
var temp;
//以等倍數(shù)間隔，調(diào)整堆為大根堆
for (; 2 * i + 1 < len; i = child){
child = 2 * i + 1; //定位其左孩子
if (child < len - 1 && arr[child + 1] > arr[child])//從其左右孩子中選擇最大的孩子
child++;
if (arr[i] < arr[child])//如果自己比最大的孩子小，和該孩子交換
[arr[child], arr[i]] = [arr[i], arr[child]];
else
break;
}
}
}
基數(shù)排序(桶排序)
這個(gè)排序是對(duì)費(fèi)空間的，不過(guò)這個(gè)思想有點(diǎn)像哈希表的意思。顧名思義，它是透過(guò)鍵值的部份資訊，比如每個(gè)數(shù)的最高位(如果位數(shù)不同在前方補(bǔ)零)，將要排序的元素分配至某些“桶”中，依次從低位到高位執(zhí)行，然后再把每個(gè)桶的數(shù)據(jù)順序綜合起來(lái)，以達(dá)到排序的作用。就像下圖這樣，可以理解桶的意思：
下圖是整個(gè)排序過(guò)程示意圖：
基數(shù)排序時(shí)間復(fù)雜度為，空間復(fù)雜度為
，屬于 穩(wěn)定 排序。（其中r為基數(shù)，n為數(shù)據(jù)總數(shù)，d為桶數(shù)；也有書(shū)得到其平均時(shí)間復(fù)雜度為
）
//基數(shù)排序(桶排序)
radixSort = function(arr){
var len = arr.length;
var bullet= [];
var k=1, temp;//k是處理數(shù)字的權(quán)重，k=1表示處理個(gè)位數(shù)，k=10表示處理十位數(shù)，以此類推
for (var i = 0; i < 10; i++)//為每個(gè)桶分配內(nèi)存空間
bullet[i] = [];
while (true){
var num = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ];//num用來(lái)統(tǒng)計(jì)0~9每個(gè)桶里面現(xiàn)有數(shù)字個(gè)數(shù)
for (var i = 0; i < len; i++){//統(tǒng)計(jì)分配每個(gè)數(shù)字到桶里面，并統(tǒng)計(jì)每個(gè)桶數(shù)字個(gè)數(shù)
temp = Math.floor(arr[i] / k) % 10;
bullet[temp][num[temp]++] = arr[i];
}
if (num[0] == len) break;//當(dāng)全部數(shù)字都在編號(hào)為0的桶中，排序結(jié)束
//將桶里的數(shù)依次放回a數(shù)組中
for (var i = 0; i < len; i++){
for (var j = 0; j < 10; j++){
for (var r = 0; r < num[j]; r++)
arr[i++] = bullet[j][r];
}
}
k *= 10;//k增加10倍，從右至左處理下一位數(shù)字
}
return arr;
}
排序?qū)Ρ?/h2>
以上是常見(jiàn)的8種排序算法，小編也把結(jié)果寫(xiě)出來(lái)把。下面是10個(gè)隨機(jī)數(shù)的排序效果：
當(dāng)然還有算法速度，小編用了2萬(wàn)個(gè)均勻分布在0到10000的隨機(jī)數(shù)，得到如下結(jié)果：
不過(guò)實(shí)際使用中，并不是越快越好，而且即便是追求快也和數(shù)據(jù)本身的質(zhì)量有關(guān)系。就像下面這個(gè)表中的：
| 算法 | 時(shí)間復(fù)雜度(最好) | 時(shí)間復(fù)雜度(最好) | 時(shí)間復(fù)雜度(最壞) | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n^(1.3)) | O(n) | O(n^2) | O(1) | 不穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 基數(shù)排序 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | O(n+rd) | 穩(wěn)定 |
注:
- 基數(shù)排序的復(fù)雜度中，r 代表關(guān)鍵字基數(shù)，d 代表長(zhǎng)度，n 代表關(guān)鍵字個(gè)數(shù)
- 排序算法的穩(wěn)定性指在原序列中，ri=rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
開(kāi)發(fā)的時(shí)候應(yīng)該綜合排序原始數(shù)據(jù)狀態(tài)，需求，穩(wěn)定性，系統(tǒng)資源等諸多因素來(lái)確定使用哪種排序方式，也可一將幾種排序組合使用以提高性能，比如小編就發(fā)現(xiàn)在快速排序中，當(dāng)每個(gè)部分?jǐn)?shù)據(jù)數(shù)量小于8時(shí)，對(duì)每個(gè)部分用插入排序就比一直使用快速排序更快。小編在找到一個(gè)動(dòng)圖，十分生動(dòng)形象的表現(xiàn)了不同算法的速度上的差異。
本章js源碼可以 點(diǎn)此去下載
排序算法就寫(xiě)這么多，有什么不足還請(qǐng)指點(diǎn)。
