快捷導(dǎo)航

Javascript中的常見(jiàn)排序算法

更新時(shí)間：2007年03月27日 00:00:00 作者：

用JavaScript實(shí)現(xiàn)的常見(jiàn)排序算法:冒泡排序,選擇排序,插入排序,謝爾排序,快速排序(遞歸),快速排序(堆棧),歸并排序,堆排序。

具體代碼及比較如下所示：

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  
<html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">  
<head>  
<title> 常見(jiàn)排序算法 之 JavaScript版 </title>  
<meta http-equiv="content-type" content="text/html; charset=gb2312" />  
<meta name="keywords" content="排序,算法,JavaScript排序" />  
<meta name="description" content="用JavaScript實(shí)現(xiàn)的常見(jiàn)排序算法:冒泡排序,選擇排序,插入排序,謝爾排序,快速排序(遞歸),快速排序(堆棧),歸并排序,堆排序" />  
<script type="text/javascript">  
 Array.prototype.swap = function(i, j)  
 {  
 var temp = this[i];  
 this[i] = this[j];  
 this[j] = temp;  
 }  
 Array.prototype.bubbleSort = function()  
 {  
 for (var i = this.length - 1; i > 0; --i)  
 {  
 for (var j = 0; j < i; ++j)  
 {  
 if (this[j] > this[j + 1]) this.swap(j, j + 1);  
 }  
 }  
 }  
 Array.prototype.selectionSort = function()  
 {  
 for (var i = 0; i < this.length; ++i)  
 {  
 var index = i;  
 for (var j = i + 1; j < this.length; ++j)  
 {  
 if (this[j] < this[index]) index = j;  
 }  
 this.swap(i, index);  
 }  
 }  
 Array.prototype.insertionSort = function()  
 {  
 for (var i = 1; i < this.length; ++i)  
 {  
 var j = i, value = this[i];  
 while (j > 0 && this[j - 1] > value)  
 {  
 this[j] = this[j - 1];  
 --j;  
 }  
 this[j] = value;  
 }  
 }  
 Array.prototype.shellSort = function()  
 {  
 for (var step = this.length >> 1; step > 0; step >>= 1)  
 {  
 for (var i = 0; i < step; ++i)  
 {  
 for (var j = i + step; j < this.length; j += step)  
 {  
 var k = j, value = this[j];  
 while (k >= step && this[k - step] > value)  
 {  
 this[k] = this[k - step];  
 k -= step;  
 }  
 this[k] = value;  
 }  
 }  
 }  
 }  
 Array.prototype.quickSort = function(s, e)  
 {  
 if (s == null) s = 0;  
 if (e == null) e = this.length - 1;  
 if (s >= e) return;  
 this.swap((s + e) >> 1, e);  
 var index = s - 1;  
 for (var i = s; i <= e; ++i)  
 {  
 if (this[i] <= this[e]) this.swap(i, ++index);  
 }  
 this.quickSort(s, index - 1);  
 this.quickSort(index + 1, e);  
 }  
 Array.prototype.stackQuickSort = function()  
 {  
 var stack = [0, this.length - 1];  
 while (stack.length > 0)  
 {  
 var e = stack.pop(), s = stack.pop();  
 if (s >= e) continue;  
 this.swap((s + e) >> 1, e);  
 var index = s - 1;  
 for (var i = s; i <= e; ++i)  
 {  
 if (this[i] <= this[e]) this.swap(i, ++index);  
 }  
 stack.push(s, index - 1, index + 1, e);  
 }  
 }  
 Array.prototype.mergeSort = function(s, e, b)  
 {  
 if (s == null) s = 0;  
 if (e == null) e = this.length - 1;  
 if (b == null) b = new Array(this.length);  
 if (s >= e) return;  
 var m = (s + e) >> 1;  
 this.mergeSort(s, m, b);  
 this.mergeSort(m + 1, e, b);  
 for (var i = s, j = s, k = m + 1; i <= e; ++i)  
 {  
 b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];  
 }  
 for (var i = s; i <= e; ++i) this[i] = b[i];  
 }  
 Array.prototype.heapSort = function()  
 {  
 for (var i = 1; i < this.length; ++i)  
 {  
 for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1)  
 {  
 if (this[k] >= this[j]) break;  
 this.swap(j, k);  
 }  
 }  
 for (var i = this.length - 1; i > 0; --i)  
 {  
 this.swap(0, i);  
 for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1)  
 {  
 if (k == i || this[k] < this[k - 1]) --k;  
 if (this[k] <= this[j]) break;  
 this.swap(j, k);  
 }  
 }  
 }  
 function generate()  
 {  
 var max = parseInt(txtMax.value), count = parseInt(txtCount.value);  
 if (isNaN(max) || isNaN(count))  
 {  
 alert("個(gè)數(shù)和最大值必須是一個(gè)整數(shù)");  
 return;  
 }  
 var array = [];  
 for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max));  
 txtInput.value = array.join("\n");  
 txtOutput.value = "";  
 }  
 function demo(type)  
 {  
 var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n");  
 for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]);  
 var t1 = new Date();  
 eval("array." + type + "Sort()");  
 var t2 = new Date();  
 lblTime.innerText = t2.valueOf() - t1.valueOf();  
 txtOutput.value = array.join("\n");  
 }  
</script>  
</head>  
<body onload="generate();">  
<table style="font-size:12px;">  
<tr>  
 <td align="right">  
 <textarea id="txtInput" style="width:120px;height:500px;" readonly></textarea>  
 </td>  
 <td width="150" align="center">  
 隨機(jī)數(shù)個(gè)數(shù)<input id="txtCount" value="500" style="width:50px" /><br /><br />  
 最大隨機(jī)數(shù)<input id="txtMax" value="1000" style="width:50px" /><br /><br />  
 <button onclick="generate()">重新生成</button><br /><br /><br /><br />  
 耗時(shí)(毫秒)：<label id="lblTime"></label><br /><br /><br /><br />  
 <button onclick="demo('bubble');">冒泡排序</button><br /><br />  
 <button onclick="demo('selection');">選擇排序</button><br /><br />  
 <button onclick="demo('insertion');">插入排序</button><br /><br />  
 <button onclick="demo('shell');">謝爾排序</button><br /><br />  
 <button onclick="demo('quick');">快速排序(遞歸)</button><br /><br />  
 <button onclick="demo('stackQuick');">快速排序(堆棧)</button><br /><br />  
 <button onclick="demo('merge');">歸并排序</button><br /><br />  
 <button onclick="demo('heap');">堆排序</button><br /><br />  
 </td>  
 <td align="left">  
 <textarea id="txtOutput" style="width:120px;height:500px;" readonly></textarea>  
 </td>  
</tr>  
</table>  
</body>  
</html> 

快速排序, 插入排序, 希爾排序, 冒泡排序, quickSort, insertSort, shellSort, bubbleSort, javascript排序
說(shuō)明
寫這個(gè)主要是為了鍛煉自己，并無(wú)實(shí)際意義。
每個(gè)瀏覽器測(cè)試得出的數(shù)據(jù)會(huì)不一樣。比如我用chrome 測(cè)試一般快速排序都會(huì)最快，IE 則根據(jù)數(shù)組長(zhǎng)度有可能希爾最快。
不要用太大數(shù)據(jù)去測(cè)試冒泡排序(瀏覽器崩潰了我不管)
如果有興趣可以下載測(cè)試頁(yè)面

個(gè)人理解

冒泡排序：最簡(jiǎn)單，也最慢，貌似長(zhǎng)度小于7最優(yōu)
插入排序：比冒泡快，比快速排序和希爾排序慢，較小數(shù)據(jù)有優(yōu)勢(shì)
快速排序：這是一個(gè)非?？斓呐判蚍绞?，V8的sort方法就使用快速排序和插入排序的結(jié)合
希爾排序：在非chrome下數(shù)組長(zhǎng)度小于1000，希爾排序比快速更快
系統(tǒng)方法：在forfox下系統(tǒng)的這個(gè)方法非?？?

算法源碼

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

 
// ---------- 一些排序算法 
// js 利用sort進(jìn)行排序 
systemSort:function(array){ 
return array.sort(function(a, b){ 
return a - b; 
}); 
}, 
// 冒泡排序 
bubbleSort:function(array){ 
var i = 0, len = array.length, 
j, d; 
for(; i<len; i++){ 
for(j=0; j<len; j++){ 
if(array[i] < array[j]){ 
d = array[j]; 
array[j] = array[i]; 
array[i] = d; 
} 
} 
} 
return array; 
}, 
// 快速排序 
quickSort:function(array){ 
//var array = [8,4,6,2,7,9,3,5,74,5]; 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 0; 
var j = array.length - 1; 
var Sort = function(i, j){ 
// 結(jié)束條件 
if(i == j ){ return }; 
var key = array[i]; 
var stepi = i; // 記錄開(kāi)始位置 
var stepj = j; // 記錄結(jié)束位置 
while(j > i){ 
// j <<-------------- 向前查找 
if(array[j] >= key){ 
j--; 
}else{ 
array[i] = array[j] 
//i++ ------------>>向后查找 
while(j > ++i){ 
if(array[i] > key){ 
array[j] = array[i]; 
break; 
} 
} 
} 
} 
// 如果第一個(gè)取出的 key 是最小的數(shù) 
if(stepi == i){ 
Sort(++i, stepj); 
return ; 
} 
// 最后一個(gè)空位留給 key 
array[i] = key; 
// 遞歸 
Sort(stepi, i); 
Sort(j, stepj); 
} 
Sort(i, j); 
return array; 
}, 
// 插入排序 
insertSort:function(array){ 
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080 
// http://baike.baidu.com/view/396887.htm 
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]; 
var i = 1, j, step, key, 
len = array.length; 
for(; i < len; i++){ 
step = j = i; 
key = array[j]; 
while(--j > -1){ 
if(array[j] > key){ 
array[j+1] = array[j]; 
}else{ 
break; 
} 
} 
array[j+1] = key; 
} 
return array; 
}, 
// 希爾排序 
//Jun.array.shellSort(Jun.array.df(10000)); 
shellSort:function(array){ 
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F 
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]; 
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在維基上看到這個(gè)最優(yōu)的步長(zhǎng) 較小數(shù)組 
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//針對(duì)大數(shù)組的步長(zhǎng)選擇 
var i = 0; 
var stepArrLength = stepArr.length; 
var len = array.length; 
var len2 = parseInt(len/2); 
for(;i < stepArrLength; i++){ 
if(stepArr[i] > len2){ 
continue; 
} 
stepSort(stepArr[i]); 
} 
// 排序一個(gè)步長(zhǎng) 
function stepSort(step){ 
//console.log(step) 使用的步長(zhǎng)統(tǒng)計(jì) 
var i = 0, j = 0, f, tem, key; 
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step; 

for(;i < step; i++){// 依次循環(huán)列 
for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循環(huán)每列的每行 
tem = f = step * j + i; 
key = array[f]; 
while((tem-=step) >= 0){// 依次向上查找 
if(array[tem] > key){ 
array[tem+step] = array[tem]; 
}else{ 
break; 
} 
} 
array[tem + step ] = key; 
} 
} 
} 
return array; 
} 