JavaScript中的排序算法代碼

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

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

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

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

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

復制代碼代碼如下:

 
/** @name 冒泡排序 
* @lastmodify 2010/07/13 
* @desc 比較排序 
復雜度為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; 
} 

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

復制代碼代碼如下:

 
/** @name 快速排序 
* @lastmodify 2010/07/14 
* @desc 比較排序 
最差運行時間O(n*n); 
最好運行時間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){ 
//默認找它的中間位置 
return Math.floor((i + j) / 2); 
} 

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

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

復制代碼代碼如下:

 
/** @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; 
} 

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

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

您可能感興趣的文章: