javascript中可能用得到的全部的排序算法
導(dǎo)讀
排序算法可以稱(chēng)得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道冒泡啊?!), 要知道學(xué)習(xí)一門(mén)技術(shù)最好的時(shí)間是三年前, 但愿我現(xiàn)在補(bǔ)習(xí)還來(lái)得及(捂臉).
因此本篇重拾了出鏡概率比較高的十來(lái)種排序算法, 逐一分析其排序思想, 并批注注意事項(xiàng). 歡迎對(duì)算法提出改進(jìn)和討論.
冒泡排序
冒泡排序需要兩個(gè)嵌套的循環(huán). 其中, 外層循環(huán)移動(dòng)游標(biāo); 內(nèi)層循環(huán)遍歷游標(biāo)及之后(或之前)的元素, 通過(guò)兩兩交換的方式, 每次只確保該內(nèi)循環(huán)結(jié)束位置排序正確, 然后內(nèi)層循環(huán)周期結(jié)束, 交由外層循環(huán)往后(或前)移動(dòng)游標(biāo), 隨即開(kāi)始下一輪內(nèi)層循環(huán), 以此類(lèi)推, 直至循環(huán)結(jié)束.
Tips: 由于冒泡排序只在相鄰元素大小不符合要求時(shí)才調(diào)換他們的位置, 它并不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法.
由于有兩層循環(huán), 因此可以有四種實(shí)現(xiàn)方式.
方案 | 外層循環(huán) | 內(nèi)層循環(huán) |
---|---|---|
1 | 正序 | 正序 |
2 | 正序 | 逆序 |
3 | 逆序 | 正序 |
4 | 逆序 | 逆序 |
四種不同循環(huán)方向, 實(shí)現(xiàn)方式略有差異.
如下是動(dòng)圖效果(對(duì)應(yīng)于方案1: 內(nèi)/外層循環(huán)均是正序遍歷.
如下是上圖的算法實(shí)現(xiàn)(對(duì)應(yīng)方案一: 內(nèi)/外層循環(huán)均是正序遍歷).
//先將交換元素部分抽象出來(lái) function swap(i,j,array){ var temp = array[j]; array[j] = array[i]; array[i] = temp; }
function bubbleSort(array) { var length = array.length, isSwap; for (var i = 0; i < length; i++) { //正序 isSwap = false; for (var j = 0; j < length - 1 - i; j++) { //正序 array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array); } if(!isSwap) break; } return array; }
以上, 排序的特點(diǎn)就是: 靠后的元素位置先確定.
方案二: 外循環(huán)正序遍歷, 內(nèi)循環(huán)逆序遍歷, 代碼如下:
function bubbleSort(array) { var length = array.length, isSwap; for (var i = 0; i < length; i++) { //正序 isSwap = false; for (var j = length - 1; j >= i+1; j--) { //逆序 array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array); } if(!isSwap) break; } return array; }
以上, 靠前的元素位置先確定.
方案三: 外循環(huán)逆序遍歷, 內(nèi)循環(huán)正序遍歷, 代碼如下:
function bubbleSort(array) { var length = array.length, isSwap; for (var i = length - 1; i >= 0; i--) { //逆序 isSwap = false; for (var j = 0; j < i; j++) { //正序 array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array); } if(!isSwap) break; } return array; }
以上, 由于內(nèi)循環(huán)是正序遍歷, 因此靠后的元素位置先確定.
方案四: 外循環(huán)逆序遍歷, 內(nèi)循環(huán)逆序遍歷, 代碼如下:
function bubbleSort(array) { var length = array.length, isSwap; for (var i = length - 1; i >= 0; i--) { //逆序 isSwap = false; for (var j = length - 1; j >= length - 1 - i; j--) { //逆序 array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array); } if(!isSwap) break; } return array; }
以上, 由于內(nèi)循環(huán)是逆序遍歷, 因此靠前的元素位置先確定.
以下是其算法復(fù)雜度:
平均時(shí)間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 |
---|---|---|---|
O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易實(shí)現(xiàn)的排序, 最壞的情況是每次都需要交換, 共需遍歷并交換將近n²/2次, 時(shí)間復(fù)雜度為O(n²). 最佳的情況是內(nèi)循環(huán)遍歷一次后發(fā)現(xiàn)排序是對(duì)的, 因此退出循環(huán), 時(shí)間復(fù)雜度為O(n). 平均來(lái)講, 時(shí)間復(fù)雜度為O(n²). 由于冒泡排序中只有緩存的temp變量需要內(nèi)存空間, 因此空間復(fù)雜度為常量O(1).
雙向冒泡排序
雙向冒泡排序是冒泡排序的一個(gè)簡(jiǎn)易升級(jí)版, 又稱(chēng)雞尾酒排序. 冒泡排序是從低到高(或者從高到低)單向排序, 雙向冒泡排序顧名思義就是從兩個(gè)方向分別排序(通常, 先從低到高, 然后從高到低). 因此它比冒泡排序性能稍好一些.
如下是算法實(shí)現(xiàn):
function bothwayBubbleSort(array){ var tail = array.length-1, i, isSwap = false; for(i = 0; i < tail; tail--){ for(var j = tail; j > i; j--){ //第一輪, 先將最小的數(shù)據(jù)冒泡到前面 array[j-1] > array[j] && (isSwap = true) && swap(j,j-1,array); } i++; for(j = i; j < tail; j++){ //第二輪, 將最大的數(shù)據(jù)冒泡到后面 array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array); } } return array; }
選擇排序
從算法邏輯上看, 選擇排序是一種簡(jiǎn)單且直觀的排序算法. 它也是兩層循環(huán). 內(nèi)層循環(huán)就像工人一樣, 它是真正做事情的, 內(nèi)層循環(huán)每執(zhí)行一遍, 將選出本次待排序的元素中最小(或最大)的一個(gè), 存放在數(shù)組的起始位置. 而 外層循環(huán)則像老板一樣, 它告訴內(nèi)層循環(huán)你需要不停的工作, 直到工作完成(也就是全部的元素排序完成).
Tips: 選擇排序每次交換的元素都有可能不是相鄰的, 因此它有可能打破原來(lái)值為相同的元素之間的順序. 比如數(shù)組[2,2,1,3], 正向排序時(shí), 第一個(gè)數(shù)字2將與數(shù)字1交換, 那么兩個(gè)數(shù)字2之間的順序?qū)⒑驮瓉?lái)的順序不一致, 雖然它們的值相同, 但它們相對(duì)的順序卻發(fā)生了變化. 我們將這種現(xiàn)象稱(chēng)作 不穩(wěn)定性 .
如下是動(dòng)圖效果:
如下是上圖的算法實(shí)現(xiàn):
function selectSort(array) { var length = array.length, min; for (var i = 0; i < length - 1; i++) { min = i; for (var j = i + 1; j < length; j++) { array[j] < array[min] && (min = j); //記住最小數(shù)的下標(biāo) } min!=i && swap(i,min,array); } return array; }
以下是其算法復(fù)雜度:
平均時(shí)間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 |
---|---|---|---|
O(n²) | O(n²) | O(n²) | O(1) |
選擇排序的簡(jiǎn)單和直觀名副其實(shí), 這也造就了它”出了名的慢性子”, 無(wú)論是哪種情況, 哪怕原數(shù)組已排序完成, 它也將花費(fèi)將近n²/2次遍歷來(lái)確認(rèn)一遍. 即便是這樣, 它的排序結(jié)果也還是不穩(wěn)定的. 唯一值得高興的是, 它并不耗費(fèi)額外的內(nèi)存空間.
插入排序
插入排序的設(shè)計(jì)初衷是往有序的數(shù)組中快速插入一個(gè)新的元素. 它的算法思想是: 把要排序的數(shù)組分為了兩個(gè)部分, 一部分是數(shù)組的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先將第一部分排序完成, 然后再插入這個(gè)元素. 其中第一部分的排序也是通過(guò)再次拆分為兩部分來(lái)進(jìn)行的.
插入排序由于操作不盡相同, 可分為 直接插入排序 , 折半插入排序(又稱(chēng)二分插入排序), 鏈表插入排序 , 希爾排序 .
直接插入排序
它的基本思想是: 將待排序的元素按照大小順序, 依次插入到一個(gè)已經(jīng)排好序的數(shù)組之中, 直到所有的元素都插入進(jìn)去.
如下是動(dòng)圖效果:
如下是上圖的算法實(shí)現(xiàn):
function directInsertionSort(array) { var length = array.length, index, current; for (var i = 1; i < length; i++) { index = i - 1; //待比較元素的下標(biāo) current = array[i]; //當(dāng)前元素 while(index >= 0 && array[index] > current) { //前置條件之一:待比較元素比當(dāng)前元素大 array[index+1] = array[index]; //將待比較元素后移一位 index--; //游標(biāo)前移一位 //console.log(array); } if(index+1 != i){ //避免同一個(gè)元素賦值給自身 array[index+1] = current; //將當(dāng)前元素插入預(yù)留空位 //console.log(array); } } return array; }
為了更好的觀察到直接插入排序的實(shí)現(xiàn)過(guò)程, 我們不妨將上述代碼中的注釋部分加入. 以數(shù)組 [5,4,3,2,1] 為例, 如下便是原數(shù)組的演化過(guò)程.
可見(jiàn), 數(shù)組的各個(gè)元素, 從后往前, 只要比前面的元素小, 都依次插入到了合理的位置.
Tips: 由于直接插入排序每次只移動(dòng)一個(gè)元素的位置, 并不會(huì)改變值相同的元素之間的排序, 因此它是一種穩(wěn)定排序.
折半插入排序
折半插入排序是直接插入排序的升級(jí)版. 鑒于插入排序第一部分為已排好序的數(shù)組, 我們不必按順序依次尋找插入點(diǎn), 只需比較它們的中間值與待插入元素的大小即可.
Tips: 同直接插入排序類(lèi)似, 折半插入排序每次交換的是相鄰的且值為不同的元素, 它并不會(huì)改變值相同的元素之間的順序. 因此它是穩(wěn)定的.
算法基本思想是:
- 取0 ~ i-1的中間點(diǎn)( m = (i-1)>>1 ), array[i] 與 array[m] 進(jìn)行比較, 若array[i] < array[m] , 則說(shuō)明待插入的元素array[i] 應(yīng)該處于數(shù)組的 0 ~ m 索引之間; 反之, 則說(shuō)明它應(yīng)該處于數(shù)組的 m ~ i-1 索引之間.
- 重復(fù)步驟1, 每次縮小一半的查找范圍, 直至找到插入的位置.
- 將數(shù)組中插入位置之后的元素全部后移一位.
- 在指定位置插入第 i 個(gè)元素.
注: x>>1 是位運(yùn)算中的右移運(yùn)算, 表示右移一位, 等同于x除以2再取整, 即 x>>1 == Math.floor(x/2) .
如下是算法實(shí)現(xiàn):
function binaryInsertionSort(array){ var current, i, j, low, high, m; for(i = 1; i < array.length; i++){ low = 0; high = i - 1; current = array[i]; while(low <= high){ //步驟1&2:折半查找 m = (low + high)>>1; if(array[i] >= array[m]){//值相同時(shí), 切換到高半?yún)^(qū),保證穩(wěn)定性 low = m + 1; //插入點(diǎn)在高半?yún)^(qū) }else{ high = m - 1; //插入點(diǎn)在低半?yún)^(qū) } } for(j = i; j > low; j--){ //步驟3:插入位置之后的元素全部后移一位 array[j] = array[j-1]; } array[low] = current; //步驟4:插入該元素 } return array; }
為了便于對(duì)比, 同樣以數(shù)組 [5,4,3,2,1] 舉例🌰. 原數(shù)組的演化過(guò)程如下(與上述一樣):
雖然折半插入排序明顯減少了查詢(xún)的次數(shù), 但是數(shù)組元素移動(dòng)的次數(shù)卻沒(méi)有改變. 它們的時(shí)間復(fù)雜度都是O(n²).
希爾排序
希爾排序也稱(chēng)縮小增量排序, 它是直接插入排序的另外一個(gè)升級(jí)版, 實(shí)質(zhì)就是分組插入排序. 希爾排序以其設(shè)計(jì)者希爾(Donald Shell)的名字命名, 并于1959年公布.
算法的基本思想:
- 將數(shù)組拆分為若干個(gè)子分組, 每個(gè)分組由相距一定”增量”的元素組成. 比方說(shuō)將[0,1,2,3,4,5,6,7,8,9,10]的數(shù)組拆分為”增量”為5的分組, 那么子分組分別為 [0,5], [1,6], [2,7], [3,8], [4,9] 和 [5,10].
- 然后對(duì)每個(gè)子分組應(yīng)用直接插入排序.
- 逐步減小”增量”, 重復(fù)步驟1,2.
- 直至”增量”為1, 這是最后一個(gè)排序, 此時(shí)的排序, 也就是對(duì)全數(shù)組進(jìn)行直接插入排序.
如下是排序的示意圖:
可見(jiàn), 希爾排序?qū)嶋H上就是不斷的進(jìn)行直接插入排序, 分組是為了先將局部元素有序化. 因?yàn)橹苯硬迦肱判蛟谠鼗居行虻臓顟B(tài)下, 效率非常高. 而希爾排序呢, 通過(guò)先分組后排序的方式, 制造了直接插入排序高效運(yùn)行的場(chǎng)景. 因此希爾排序效率更高.
我們?cè)囍橄蟪龉餐c(diǎn), 便不難發(fā)現(xiàn)上述希爾排序的第四步就是一次直接插入排序, 而希爾排序原本就是從”增量”為n開(kāi)始, 直至”增量”為1, 循環(huán)應(yīng)用直接插入排序的一種封裝. 因此直接插入排序就可以看做是步長(zhǎng)為1的希爾排序. 為此我們先來(lái)封裝下直接插入排序.
//形參增加步數(shù)gap(實(shí)際上就相當(dāng)于gap替換了原來(lái)的數(shù)字1) function directInsertionSort(array, gap) { gap = (gap == undefined) ? 1 : gap; //默認(rèn)從下標(biāo)為1的元素開(kāi)始遍歷 var length = array.length, index, current; for (var i = gap; i < length; i++) { index = i - gap; //待比較元素的下標(biāo) current = array[i]; //當(dāng)前元素 while(index >= 0 && array[index] > current) { //前置條件之一:待比較元素比當(dāng)前元素大 array[index + gap] = array[index]; //將待比較元素后移gap位 index -= gap; //游標(biāo)前移gap位 } if(index + gap != i){ //避免同一個(gè)元素賦值給自身 array[index + gap] = current; //將當(dāng)前元素插入預(yù)留空位 } } return array; }
那么希爾排序的算法實(shí)現(xiàn)如下:
function shellSort(array){ var length = array.length, gap = length>>1, current, i, j; while(gap > 0){ directInsertionSort(array, gap); //按指定步長(zhǎng)進(jìn)行直接插入排序 gap = gap>>1; } return array; }
同樣以數(shù)組[5,4,3,2,1] 舉例🌰. 原數(shù)組的演化過(guò)程如下:
對(duì)比上述直接插入排序和折半插入排序, 數(shù)組元素的移動(dòng)次數(shù)由14次減少為7次. 通過(guò)拆分原數(shù)組為粒度更小的子數(shù)組, 希爾排序進(jìn)一步提高了排序的效率.
不僅如此, 以上步長(zhǎng)設(shè)置為了 {N/2, (N/2)/2, …, 1}. 該序列即希爾增量, 其它的增量序列 還有Hibbard:{1, 3, …, 2^k-1}. 通過(guò)合理調(diào)節(jié)步長(zhǎng), 還能進(jìn)一步提升排序效率. 實(shí)際上已知的最好步長(zhǎng)序列是由Sedgewick提出的(1, 5, 19, 41, 109,…). 該序列中的項(xiàng)或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1. 具體請(qǐng)戳 希爾排序-維基百科 .
Tips: 我們知道, 單次直接插入排序是穩(wěn)定的, 它不會(huì)改變相同元素之間的相對(duì)順序, 但在多次不同的插入排序過(guò)程中, 相同的元素可能在各自的插入排序中移動(dòng), 可能導(dǎo)致相同元素相對(duì)順序發(fā)生變化. 因此, 希爾排序并不穩(wěn)定.
歸并排序
歸并排序建立在歸并操作之上, 它采取分而治之的思想, 將數(shù)組拆分為兩個(gè)子數(shù)組, 分別排序, 最后才將兩個(gè)子數(shù)組合并; 拆分的兩個(gè)子數(shù)組, 再繼續(xù)遞歸拆分為更小的子數(shù)組, 進(jìn)而分別排序, 直到數(shù)組長(zhǎng)度為1, 直接返回該數(shù)組為止.
Tips: 歸并排序嚴(yán)格按照從左往右(或從右往左)的順序去合并子數(shù)組, 它并不會(huì)改變相同元素之間的相對(duì)順序, 因此它也是一種穩(wěn)定的排序算法.
如下是動(dòng)圖效果:
歸并排序可通過(guò)兩種方式實(shí)現(xiàn):
- 自上而下的遞歸
- 自下而上的迭代
如下是算法實(shí)現(xiàn)(方式1:遞歸):
function mergeSort(array) { //采用自上而下的遞歸方法 var length = array.length; if(length < 2) { return array; } var m = (length >> 1), left = array.slice(0, m), right = array.slice(m); //拆分為兩個(gè)子數(shù)組 return merge(mergeSort(left), mergeSort(right));//子數(shù)組繼續(xù)遞歸拆分,然后再合并 } function merge(left, right){ //合并兩個(gè)子數(shù)組 var result = []; while (left.length && right.length) { var item = left[0] <= right[0] ? left.shift() : right.shift();//注意:判斷的條件是小于或等于,如果只是小于,那么排序?qū)⒉环€(wěn)定. result.push(item); } return result.concat(left.length ? left : right); }
由上, 長(zhǎng)度為n的數(shù)組, 最終會(huì)調(diào)用mergeSort函數(shù)2n-1次. 通過(guò)自上而下的遞歸實(shí)現(xiàn)的歸并排序, 將存在堆棧溢出的風(fēng)險(xiǎn). 親測(cè)各瀏覽器的堆棧溢出所需的遞歸調(diào)用次數(shù)大致為:
Chrome v55: 15670
Firefox v50: 44488
Safari v9.1.2: 50755
以下是測(cè)試代碼:
function computeMaxCallStackSize() { try { return 1 + computeMaxCallStackSize(); } catch (e) { // Call stack overflow return 1; } } var time = computeMaxCallStackSize(); console.log(time);
為此, ES6規(guī)范中提出了尾調(diào)優(yōu)化的思想: 如果一個(gè)函數(shù)的最后一步也是一個(gè)函數(shù)調(diào)用, 那么該函數(shù)所需要的??臻g將被釋放, 它將直接進(jìn)入到下次調(diào)用中, 最終調(diào)用棧里只保留最后一次的調(diào)用記錄.
雖然ES6規(guī)范如此誘人, 然而目前并沒(méi)有瀏覽器支持尾調(diào)優(yōu)化, 相信在不久的將來(lái), 尾調(diào)優(yōu)化就會(huì)得到主流瀏覽器的支持.
以下是其算法復(fù)雜度:
平均時(shí)間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 |
---|---|---|---|
O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) |
從效率上看, 歸并排序可算是排序算法中的”佼佼者”. 假設(shè)數(shù)組長(zhǎng)度為n, 那么拆分?jǐn)?shù)組共需logn步, 又每步都是一個(gè)普通的合并子數(shù)組的過(guò)程, 時(shí)間復(fù)雜度為O(n), 故其綜合時(shí)間復(fù)雜度為O(nlogn). 另一方面, 歸并排序多次遞歸過(guò)程中拆分的子數(shù)組需要保存在內(nèi)存空間, 其空間復(fù)雜度為O(n).
快速排序
快速排序借用了分治的思想, 并且基于冒泡排序做了改進(jìn). 它由C. A. R. Hoare在1962年提出. 它將數(shù)組拆分為兩個(gè)子數(shù)組, 其中一個(gè)子數(shù)組的所有元素都比另一個(gè)子數(shù)組的元素小, 然后對(duì)這兩個(gè)子數(shù)組再重復(fù)進(jìn)行上述操作, 直到數(shù)組不可拆分, 排序完成.
如下是動(dòng)圖效果:
如下是算法實(shí)現(xiàn):
function quickSort(array, left, right) { var partitionIndex, left = typeof left == 'number' ? left : 0, right = typeof right == 'number' ? right : array.length-1; if (left < right) { partitionIndex = partition(array, left, right);//切分的基準(zhǔn)值 quickSort(array, left, partitionIndex-1); quickSort(array, partitionIndex+1, right); } return array; } function partition(array, left ,right) { //分區(qū)操作 for (var i = left+1, j = left; i <= right; i++) {//j是較小值存儲(chǔ)位置的游標(biāo) array[i] < array[left] && swap(i, ++j, array);//以第一個(gè)元素為基準(zhǔn) } swap(left, j, array); //將第一個(gè)元素移至中間 return j; }
以下是其算法復(fù)雜度:
平均時(shí)間復(fù)雜度 | 最好情況 | 最壞情況 | 空間復(fù)雜度 |
---|---|---|---|
O(nlog₂n) | O(nlog₂n) | O(n²) | O(nlog₂n) |
快速排序排序效率非常高. 雖然它運(yùn)行最糟糕時(shí)將達(dá)到O(n²)的時(shí)間復(fù)雜度, 但通常, 平均來(lái)看, 它的時(shí)間復(fù)雜為O(nlogn), 比同樣為O(nlogn)時(shí)間復(fù)雜度的歸并排序還要快. 快速排序似乎更偏愛(ài)亂序的數(shù)列, 越是亂序的數(shù)列, 它相比其他排序而言, 相對(duì)效率更高. 之前在 捋一捋JS的數(shù)組 一文中就提到: Chrome的v8引擎為了高效排序, 在排序數(shù)據(jù)超過(guò)了10條時(shí), 便會(huì)采用快速排序. 對(duì)于10條及以下的數(shù)據(jù)采用的便是插入排序.
Tips: 同選擇排序相似, 快速排序每次交換的元素都有可能不是相鄰的, 因此它有可能打破原來(lái)值為相同的元素之間的順序. 因此, 快速排序并不穩(wěn)定.
堆排序
1991年的計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert W.Floyd) 和威廉姆斯(J.Williams) 在1964年共同發(fā)明了著名的堆排序算法(Heap Sort).
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法. 它是選擇排序的一種. 堆分為大根堆和小根堆. 大根堆要求每個(gè)子節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值, 即array[childIndex] <= array[parentIndex], 最大的值一定在堆頂. 小根堆與之相反, 即每個(gè)子節(jié)點(diǎn)的值都不小于其父節(jié)點(diǎn)的值, 最小的值一定在堆頂. 因此我們可使用大根堆進(jìn)行升序排序, 使用小根堆進(jìn)行降序排序.
并非所有的序列都是堆, 對(duì)于序列k1, k2,…kn, 需要滿(mǎn)足如下條件才行:
ki <= k(2i) 且 ki<=k(2i+1)(1≤i≤ n/2), 即為小根堆, 將<=換成>=, 那么則是大根堆. 我們可以將這里的堆看作完全二叉樹(shù), k(i) 相當(dāng)于是二叉樹(shù)的非葉子節(jié)點(diǎn), k(2i) 則是左子節(jié)點(diǎn), k(2i+1)是右子節(jié)點(diǎn).
算法的基本思想(以大根堆為例):
- 先將初始序列K[1..n]建成一個(gè)大根堆, 此堆為初始的無(wú)序區(qū).
- 再將關(guān)鍵字最大的記錄K1 (即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄K[n]交換, 由此得到新的無(wú)序區(qū)K[1..n-1]和有序區(qū)K[n], 且滿(mǎn)足K[1..n-1].keys≤K[n].key
- 交換K1 和 K[n] 后, 堆頂可能違反堆性質(zhì), 因此需將K[1..n-1]調(diào)整為堆. 然后重復(fù)步驟2, 直到無(wú)序區(qū)只有一個(gè)元素時(shí)停止.
如下是動(dòng)圖效果:
如下是算法實(shí)現(xiàn):
function heapAdjust(array, i, length) {//堆調(diào)整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < length && array[largest] < array[left]) { largest = left; } if (right < length && array[largest] < array[right]) { largest = right; } if (largest != i) { swap(i, largest, array); heapAdjust(array, largest, length); } } function heapSort(array) { //建立大頂堆 length = array.length; for (var i = length>>1; i >= 0; i--) { heapAdjust(array, i, length); } //調(diào)換第一個(gè)與最后一個(gè)元素,重新調(diào)整為大頂堆 for (var i = length - 1; i > 0; i--) { swap(0, i, array); heapAdjust(array, 0, --length); } return array; }
以上, ①建立堆的過(guò)程, 從length/2 一直處理到0, 時(shí)間復(fù)雜度為O(n);
②調(diào)整堆的過(guò)程是沿著堆的父子節(jié)點(diǎn)進(jìn)行調(diào)整, 執(zhí)行次數(shù)為堆的深度, 時(shí)間復(fù)雜度為O(lgn);
③堆排序的過(guò)程由n次第②步完成, 時(shí)間復(fù)雜度為O(nlgn).
Tips: 由于堆排序中初始化堆的過(guò)程比較次數(shù)較多, 因此它不太適用于小序列. 同時(shí)由于多次任意下標(biāo)相互交換位置, 相同元素之間原本相對(duì)的順序被破壞了, 因此, 它是不穩(wěn)定的排序.
計(jì)數(shù)排序
計(jì)數(shù)排序幾乎是唯一一個(gè)不基于比較的排序算法, 該算法于1954年由 Harold H. Seward 提出. 使用它處理一定范圍內(nèi)的整數(shù)排序時(shí), 時(shí)間復(fù)雜度為O(n+k), 其中k是整數(shù)的范圍, 它幾乎比任何基于比較的排序算法都要快( 只有當(dāng)O(k)>O(n*log(n))的時(shí)候其效率反而不如基于比較的排序, 如歸并排序和堆排序).
使用計(jì)數(shù)排序需要滿(mǎn)足如下條件:
- 待排序的序列全部為整數(shù)
- 排序需要額外的存儲(chǔ)空間
算法的基本思想:
計(jì)數(shù)排序利用了一個(gè)特性, 對(duì)于數(shù)組的某個(gè)元素, 一旦知道了有多少個(gè)其它元素比它小(假設(shè)為m個(gè)), 那么就可以確定出該元素的正確位置(第m+1位)
- 獲取待排序數(shù)組A的最大值, 最小值.
- 將最大值與最小值的差值+1作為長(zhǎng)度新建計(jì)數(shù)數(shù)組B,并將相同元素的數(shù)量作為值存入計(jì)數(shù)數(shù)組.
- 對(duì)計(jì)數(shù)數(shù)組B累加計(jì)數(shù), 存儲(chǔ)不同值的初始下標(biāo).
- 從原數(shù)組A挨個(gè)取值, 賦值給一個(gè)新的數(shù)組C相應(yīng)的下標(biāo), 最終返回?cái)?shù)組C.
注意: 如果原數(shù)組A是包含若干個(gè)對(duì)象的數(shù)組,需要基于對(duì)象的某個(gè)屬性進(jìn)行排序,那么算法開(kāi)始時(shí),需要將原數(shù)組A處理為一個(gè)只包含對(duì)象屬性值的簡(jiǎn)單數(shù)組simpleA, 接下來(lái)便基于simpleA進(jìn)行計(jì)數(shù)、累加計(jì)數(shù), 其它同上.
如下是動(dòng)圖效果:
如下是算法實(shí)現(xiàn):
function countSort(array, keyName){ var length = array.length, output = new Array(length), max, min, simpleArray = keyName ? array.map(function(v){ return v[keyName]; }) : array; // 如果keyName是存在的,那么就創(chuàng)建一個(gè)只有keyValue的簡(jiǎn)單數(shù)組 // 獲取最大最小值 max = min = simpleArray[0]; simpleArray.forEach(function(v){ v > max && (max = v); v < min && (min = v); }); // 獲取計(jì)數(shù)數(shù)組的長(zhǎng)度 var k = max - min + 1; // 新建并初始化計(jì)數(shù)數(shù)組 var countArray = new Array(k); simpleArray.forEach(function(v){ countArray[v - min]= (countArray[v - min] || 0) + 1; }); // 累加計(jì)數(shù),存儲(chǔ)不同值的初始下標(biāo) countArray.reduce(function(prev, current, i, arr){ arr[i] = prev; return prev + current; }, 0); // 從原數(shù)組挨個(gè)取值(因取的是原數(shù)組的相應(yīng)值,只能通過(guò)遍歷原數(shù)組來(lái)實(shí)現(xiàn)) simpleArray.forEach(function(v, i){ var j = countArray[v - min]++; output[j] = array[i]; }); return output; }
以上實(shí)現(xiàn)不僅支持了數(shù)值序列的排序,還支持根據(jù)對(duì)象的某個(gè)屬性值來(lái)排序。測(cè)試如下:
var a = [2, 1, 1, 3, 2, 1, 4, 2], b = [ {id: 2, s:'a'}, {id: 1, s: 'b'}, {id: 1, s: 'c'}, {id: 3, s: 'd'}, {id: 2, s: 'e'}, {id: 1, s: 'f'}, {id: 4, s: 'g'}, {id: 2, s: 'h'} ]; countSort(a); // [1, 1, 1, 2, 2, 2, 3, 4] countSort(b, 'id'); // [{id:1,s:'b'},{id:1,s:'c'},{id:1,s:'f'},{id:2,s:'a'},{id:2,s:'e'},{id:2,s:'h'},{id:3,s:'d'},{id:4,s:'g'}]
Tips: 計(jì)數(shù)排序不改變相同元素之間原本相對(duì)的順序, 因此它是穩(wěn)定的排序算法.
桶排序
桶排序即所謂的箱排序, 它是將數(shù)組分配到有限數(shù)量的桶子里. 每個(gè)桶里再各自排序(因此有可能使用別的排序算法或以遞歸方式繼續(xù)桶排序). 當(dāng)每個(gè)桶里的元素個(gè)數(shù)趨于一致時(shí), 桶排序只需花費(fèi)O(n)的時(shí)間. 桶排序通過(guò)空間換時(shí)間的方式提高了效率, 因此它需要額外的存儲(chǔ)空間(即桶的空間).
算法的基本思想:
桶排序的核心就在于怎么把元素平均分配到每個(gè)桶里, 合理的分配將大大提高排序的效率.
如下是算法實(shí)現(xiàn):
function bucketSort(array, bucketSize) { if (array.length === 0) { return array; } var i = 1, min = array[0], max = min; while (i++ < array.length) { if (array[i] < min) { min = array[i]; //輸入數(shù)據(jù)的最小值 } else if (array[i] > max) { max = array[i]; //輸入數(shù)據(jù)的最大值 } } //桶的初始化 bucketSize = bucketSize || 5; //設(shè)置桶的默認(rèn)大小為5 var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的個(gè)數(shù) buckets = new Array(bucketCount); //創(chuàng)建桶 for (i = 0; i < buckets.length; i++) { buckets[i] = []; //初始化桶 } //將數(shù)據(jù)分配到各個(gè)桶中,這里直接按照數(shù)據(jù)值的分布來(lái)分配,一定范圍內(nèi)均勻分布的數(shù)據(jù)效率最為高效 for (i = 0; i < array.length; i++) { buckets[~~((array[i] - min) / bucketSize)].push(array[i]); } array.length = 0; for (i = 0; i < buckets.length; i++) { quickSort(buckets[i]); //對(duì)每個(gè)桶進(jìn)行排序,這里使用了快速排序 for (var j = 0; j < buckets[i].length; j++) { array.push(buckets[i][j]); //將已排序的數(shù)據(jù)寫(xiě)回?cái)?shù)組中 } } return array; }
Tips: 桶排序本身是穩(wěn)定的排序, 因此它的穩(wěn)定性與桶內(nèi)排序的穩(wěn)定性保持一致.
實(shí)際上, 桶也只是一個(gè)抽象的概念, 它的思想與歸并排序,快速排序等類(lèi)似, 都是通過(guò)將大量數(shù)據(jù)分配到N個(gè)不同的容器中, 分別排序, 最后再合并數(shù)據(jù). 這種方式大大減少了排序時(shí)整體的遍歷次數(shù), 提高了算法效率.
基數(shù)排序
基數(shù)排序源于老式穿孔機(jī), 排序器每次只能看到一個(gè)列. 它是基于元素值的每個(gè)位上的字符來(lái)排序的. 對(duì)于數(shù)字而言就是分別基于個(gè)位, 十位, 百位 或千位等等數(shù)字來(lái)排序. (不明白不要緊, 我也不懂, 請(qǐng)接著往下讀)
按照優(yōu)先從高位或低位來(lái)排序有兩種實(shí)現(xiàn)方案:
- MSD: 由高位為基底, 先按k1排序分組, 同一組中記錄, 關(guān)鍵碼k1相等, 再對(duì)各組按k2排序分成子組, 之后, 對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組, 直到按最次位關(guān)鍵碼kd對(duì)各子組排序后. 再將各組連接起來(lái), 便得到一個(gè)有序序列. MSD方式適用于位數(shù)多的序列.
- LSD: 由低位為基底, 先從kd開(kāi)始排序,再對(duì)kd-1進(jìn)行排序,依次重復(fù),直到對(duì)k1排序后便得到一個(gè)有序序列. LSD方式適用于位數(shù)少的序列.
如下是LSD的動(dòng)圖效果:
如下是算法實(shí)現(xiàn):
function radixSort(array, max) { var buckets = [], unit = 10, base = 1; for (var i = 0; i < max; i++, base *= 10, unit *= 10) { for(var j = 0; j < array.length; j++) { var index = ~~((array[j] % unit) / base);//依次過(guò)濾出個(gè)位,十位等等數(shù)字 if(buckets[index] == null) { buckets[index] = []; //初始化桶 } buckets[index].push(array[j]);//往不同桶里添加數(shù)據(jù) } var pos = 0, value; for(var j = 0, length = buckets.length; j < length; j++) { if(buckets[j] != null) { while ((value = buckets[j].shift()) != null) { array[pos++] = value; //將不同桶里數(shù)據(jù)挨個(gè)撈出來(lái),為下一輪高位排序做準(zhǔn)備,由于靠近桶底的元素排名靠前,因此從桶底先撈 } } } } return array; }
以上算法, 如果用來(lái)比較時(shí)間, 先按日排序, 再按月排序, 最后按年排序, 僅需排序三次.
基數(shù)排序更適合用于對(duì)時(shí)間, 字符串等這些整體權(quán)值未知的數(shù)據(jù)進(jìn)行排序.
Tips: 基數(shù)排序不改變相同元素之間的相對(duì)順序, 因此它是穩(wěn)定的排序算法.
小結(jié)
各種排序性能對(duì)比如下:
排序類(lèi)型 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
---|---|---|---|---|---|
冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 穩(wěn)定 |
選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 不穩(wěn)定 |
直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩(wěn)定 |
折半插入排序 | O(n²) | O(n) | O(n²) | O(1) | 穩(wěn)定 |
希爾排序 | O(n^1.3) | O(nlogn) | O(n²) | O(1) | 不穩(wěn)定 |
歸并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) | 穩(wěn)定 |
快速排序 | O(nlog₂n) | O(nlog₂n) | O(n²) | O(nlog₂n) | 不穩(wěn)定 |
堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | 不穩(wěn)定 |
計(jì)數(shù)排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 穩(wěn)定 |
桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | (不)穩(wěn)定 |
基數(shù)排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+kd)) | O(n+kd) | 穩(wěn)定 |
注: 桶排序的穩(wěn)定性取決于桶內(nèi)排序的穩(wěn)定性, 因此其穩(wěn)定性不確定. 基數(shù)排序中, k代表關(guān)鍵字的基數(shù), d代表長(zhǎng)度, n代表關(guān)鍵字的個(gè)數(shù).
愿以此文懷念下我那遠(yuǎn)去的算法課程.
未完待續(xù)…
感謝 http://visualgo.net/ 提供圖片支持. 特別感謝 不是小羊的肖恩 在簡(jiǎn)書(shū)上發(fā)布的 JS家的排序算法 提供的講解.
- JavaScript算法學(xué)習(xí)之冒泡排序和選擇排序
- JavaScript實(shí)現(xiàn)的九種排序算法
- JavaScript插入排序算法原理與實(shí)現(xiàn)方法示例
- JavaScript選擇排序算法原理與實(shí)現(xiàn)方法示例
- 常用的 JS 排序算法 整理版
- JS排序算法之冒泡排序,選擇排序與插入排序?qū)嵗治?/a>
- JS排序算法之希爾排序與快速排序?qū)崿F(xiàn)方法
- javascript基本常用排序算法解析
- js算法中的排序、數(shù)組去重詳細(xì)概述
- 幾種經(jīng)典排序算法的JS實(shí)現(xiàn)方法
- Javascript中的常見(jiàn)排序算法
- javascript快速排序算法詳解
- JavaScript中幾種常見(jiàn)排序算法小結(jié)
相關(guān)文章
Bootstrap源碼解讀媒體對(duì)象、列表組和面板(10)
這篇文章主要源碼解讀了Bootstrap媒體對(duì)象、列表組和面板,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-12-12用Div仿showModalDialog模式菜單的效果的代碼
用Div仿showModalDialog模式菜單的效果的代碼...2007-03-03用最簡(jiǎn)單的方法判斷JavaScript中this的指向(推薦)
都說(shuō) JavaScript 是一種很靈活的語(yǔ)言,這其實(shí)也可以說(shuō)它是一個(gè)混亂的語(yǔ)言,下面通過(guò)本文給大家分享JavaScript中this的指向知識(shí),感興趣的朋友一起看看吧2017-09-09一個(gè)獲取第n個(gè)元素節(jié)點(diǎn)的js函數(shù)
這篇文章主要介紹了一個(gè)獲取第n個(gè)元素節(jié)點(diǎn)的js函數(shù),功能還不完善 ,需要的朋友可以參考下2014-09-09javascript實(shí)現(xiàn)貪吃蛇經(jīng)典游戲
這篇文章主要為大家詳細(xì)介紹了javascript實(shí)現(xiàn)貪吃蛇經(jīng)典游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-04-04JavaScript?數(shù)組方法filter與reduce
這篇文章主要介紹了JavaScript?數(shù)組方法filter與reduce,在ES6新增的數(shù)組方法中,包含了多個(gè)遍歷方法,其中包含了用于篩選的filter和reduce2022-07-07