快捷導(dǎo)航

JavaScript中的排序算法代碼

更新時(shí)間：2011年02月22日 21:02:50 作者：

排序算法的理解算是程序員的基本功之一了，其功能是對(duì)一個(gè)數(shù)據(jù)元素集合或序列重新排列成一個(gè)按數(shù)據(jù)元素某個(gè)項(xiàng)值有序的序列。

作為排序依據(jù)的數(shù)據(jù)項(xiàng)稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，通常希望計(jì)算機(jī)中的數(shù)據(jù)表是按關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹的構(gòu)造過程就是一個(gè)排序過程。若關(guān)鍵碼是主關(guān)鍵碼，則對(duì)于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序結(jié)果可能不唯一，這是因?yàn)榫哂邢嗤P(guān)鍵碼的數(shù)據(jù)元素，這些元素在排序結(jié)果中，它們之間的的位置關(guān)系與排序前不能保持。
若對(duì)任意的數(shù)據(jù)元素序列，使用某個(gè)排序方法，對(duì)它按關(guān)鍵碼進(jìn)行排序：若相同關(guān)鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；而不能保持一致的排序方法則稱為不穩(wěn)定的。
排序分為兩類：內(nèi)排序和外排序。
內(nèi)排序：指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過程，適合不太大的元素序列。
外排序：指排序過程中還需訪問外存儲(chǔ)器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外排序。

現(xiàn)在貼3種排序算法的JavaScript實(shí)現(xiàn)。

首先是最簡單的，是個(gè)人都會(huì)的冒泡排序。就不多說了，直接貼代碼

復(fù)制代碼代碼如下:

 
/** @name 冒泡排序 
* @lastmodify 2010/07/13 
* @desc 比較排序 
復(fù)雜度為O(n*n) 
*/ 
function BubbleSort(list){ 
var len = list.length; 
var cl,temp; 
while(len--){ 
cl = list.length; 
while(cl--){ 
if(list[cl]>list[len] && cl < len){ 
temp = list[len]; 
list[len] = list[cl]; 
list[cl] = temp; 
} 
} 
} 
return list; 
} 

然后是最常見的快速排序，面試基本上都會(huì)問到。

復(fù)制代碼代碼如下:

 
/** @name 快速排序 
* @lastmodify 2010/07/14 
* @desc 比較排序 
最差運(yùn)行時(shí)間O(n*n); 
最好運(yùn)行時(shí)間O(nlogn) 
*/ 
function QuickSort(list){ 
var i = 0; 
var j = list.length; 
var len = j; 
var left; 
var right; 
var k = findK(i , j); 
if(k != 0){ 
var leftArr = []; 
var rightArr = []; 
var midArr = [list[k]]; 
while(len--) { 
if(len != k){ 
if(list[len] > list[k]){ 
rightArr.push(list[len]); 
} 
else{ 
leftArr.push(list[len]); 
} 
} 
} 
left = QuickSort(leftArr); 
right = QuickSort(rightArr); 
list = left.concat(midArr).concat(right); 
} 
return list; 
} 

function findK(i,j){ 
//默認(rèn)找它的中間位置 
return Math.floor((i + j) / 2); 
} 

快速排序的主要思想就是分治法，將被排序的序列分割為2塊，從而將排序的復(fù)雜度降低。遞歸的巧用也是快速排序的精妙之處。在上個(gè)例子中，首先使用findK函數(shù)找出“參照元素”，其他元素依次和該元素進(jìn)行比較，所有比其大的放入一個(gè)集合中，比其小的放入另外一個(gè)集合中，再分別對(duì)兩個(gè)集合進(jìn)行排序。快速排序的效率主要取決于findK函數(shù)的實(shí)現(xiàn)和待排序元素的有序程度。因此，快速排序是一個(gè)不穩(wěn)定的排序算法。

但是快速排序仍然是一個(gè)基于比較的排序算法。所有基于比較的排序算法有一個(gè)特點(diǎn)，就是無論怎樣優(yōu)化，它對(duì)于一個(gè)元素集合的平均排序時(shí)間總是隨著該集合元素?cái)?shù)量的增加而增加。而非比較的排序很好的克服了這個(gè)缺點(diǎn)，它們?cè)噲D讓排序時(shí)間復(fù)雜度趨于一個(gè)數(shù)量無關(guān)的穩(wěn)定值。其中比較有代表性的就是桶排序了。先看看它的JavaScript實(shí)現(xiàn)。

復(fù)制代碼代碼如下:

 
/** @name 桶排序 
* @author lebron 
* @lastmodify 2010/07/15 
* @desc 非比較排序 
*/ 
function BucketSort(list) { 
var len = list.length; 
var range = findMax(list); 
var result = [], 
count = []; 
var i,j; 
for (i = 0; i < range; i++) { 
count.push(0); 
} 

for ( j = 0; j < len; j++) { 
count[list[j]]++; 
result.push(0); 
} 
for (i = 1; i < range; i++) { 
count[i] = count[i-1] + count[i]; 
} 
for (j = len - 1; j >= 0; j--) { 
result[count[list[j]]] = list[j]; 
count[list[j]]--; 
} 
return result; 
} 

function findMax(list) { 
return MAX; 
} 

可以看到，在桶排序的實(shí)現(xiàn)中，仍然使用了一個(gè)findMax函數(shù)來確定一個(gè)大數(shù)組的范圍，這里直接用一個(gè)常量MAX來代替。首先初始化一個(gè)大數(shù)組count，長度為MAX。在將被排序集合里面的值放入到對(duì)應(yīng)的位置上去，比如有一個(gè)元素值為24，那么count的第24位被標(biāo)記為1，同時(shí)result數(shù)組長度+1。再計(jì)算出count數(shù)組中標(biāo)志為1的元素位置在整個(gè)count數(shù)組中標(biāo)志為1的排位。此時(shí)count數(shù)組中，第n個(gè)元素的值，就應(yīng)當(dāng)是排序后它的位置，而n這是這個(gè)排序后這個(gè)位置對(duì)應(yīng)的值。所以，最后再一一的將count數(shù)組里面的鍵值倒過來映射入結(jié)果數(shù)組中即可。
桶排序巧妙的利用了這樣一種思想，如果一個(gè)元素它在一個(gè)集合中是第n大的，那么它應(yīng)該排第n位，而無需關(guān)心它前一位或者后一位是比它大還是比它?。o需比較）。很顯然的是，在實(shí)際情況中，被排序集合的元素的值的范圍很可能遠(yuǎn)遠(yuǎn)大于這個(gè)集合的元素?cái)?shù)量，因此，也需要分配相應(yīng)的一個(gè)巨大空間的數(shù)組才行。因此，桶排序的常見場景是在外排序上面。

有興趣的同學(xué)，可以測試下3種排序在不同數(shù)量級(jí)下的耗時(shí)。

您可能感興趣的文章: