Jquery中文網 www.2030036.live
Jquery中文網 >  腳本編程  >  javascript  >  正文 javascript排序算法代碼解析

javascript排序算法代碼解析

發布時間:2015-07-09   編輯:www.2030036.live
有關javascript排序算法的相關內容,排序算法的理解算是程序員的基本功之一了,其功能是對一個數據元素集合或序列重新排列成一個按數據元素某個項值有序的序列。

在javascript中,作為排序依據的數據項稱為“排序碼”,也即數據元素的關鍵碼。

為了便于查找,通常希望計算機中的數據表是按關鍵碼有序的。如有序表的折半查找,查找效率較高。還有,二叉排序樹、b-樹和b+樹的構造過程就是一個排序過程。若關鍵碼是主關鍵碼,則對于任意待排序序列,經排序后得到的結果是唯一的;若關鍵碼是次關鍵碼,排序結果可能不唯一,這是因為具有相同關鍵碼的數據元素,這些元素在排序結果中,它們之間的的位置關系與排序前不能保持。

若對任意的數據元素序列,使用某個排序方法,對它按關鍵碼進行排序:若相同關鍵碼元素間的位置關系,排序前與排序后保持一致,稱此排序方法是穩定的;而不能保持一致的排序方法則稱為不穩定的。
排序分為兩類:內排序和外排序。
內排序:指待排序列完全存放在內存中所進行的排序過程,適合不太大的元素序列。
外排序:指排序過程中還需訪問外存儲器,足夠大的元素序列,因不能完全放入內存,只能使用外排序。

現在貼3種排序算法的javascript實現。

1,最簡單的冒泡排序
 

復制代碼 代碼示例:
/** @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;
} // www.jquerycn.cn jquery中文網
}
}
return list;
}

2,js快速排序代碼
 

復制代碼 代碼示例:

/** @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函數找出“參照元素”,其他元素依次和該元素進行比較,所有比其大的放入一個集合中,比其小的放入另外一個集合中,再分別對兩個集合進行排序??焖倥判虻男手饕Q于findk函數的實現和待排序元素的有序程度。因此,快速排序是一個不穩定的排序算法。

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

復制代碼 代碼示例:

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

可以看到,在桶排序的實現中,仍然使用了一個findmax函數來確定一個大數組的范圍,這里直接用一個常量max來代替。首先初始化一個大數組count,長度為max。在將被排序集合里面的值放入到對應的位置上去,比如有一個元素值為24,那么count的第24位被標記為1,同時result數組長度+1。再計算出count數組中標志為1的元素位置在整個count數組中標志為1的排位。此時count數組中,第n個元素的值,就應當是排序后它的位置,而n這是這個排序后這個位置對應的值。

所以,最后再一一的將count數組里面的鍵值倒過來映射入結果數組中即可。
桶排序巧妙的利用了這樣一種思想,如果一個元素它在一個集合中是第n大的,那么它應該排第n位,而無需關心它前一位或者后一位是比它大還是比它?。o需比較)。很顯然的是,在實際情況中,被排序集合的元素的值的范圍很可能遠遠大于這個集合的元素數量,因此,也需要分配相應的一個巨大空間的數組才行。

因此,桶排序的常見場景是在外排序上面。

大家有時間可以測試下3種排序在不同數量級下的耗時。

您可能感興趣的文章:
javascript排序算法代碼解析
php冒泡排序算法一例
Javascript排序算法之計數排序實例
php冒泡排序之交換排序法
JS隨機快速排序的代碼分享
javascript常見排序算法實現代碼
php 數組排序方法分享(冒泡排序、選擇排序)
php冒泡排序與快速排序的例子
JQuery 構建客戶/服務分離的鏈接模型中Table中的排序分析
php冒泡排序(bubble sort)的例子

[關閉]
888棋牌金花app 美女捕鱼游戏 安徽麻将免费下载 三分彩彩票资讯软件 安徽闲来麻将安庆点炮苹果版 大话西游2一天赚150元 李逵劈鱼下载地址 武汉晃晃麻将规则 36选7福利彩票中奖 今天那些股票下跌 pc蛋蛋刷蛋器