首頁 web前端 js教程 Javascript中的常见排序算法_javascript技巧

Javascript中的常见排序算法_javascript技巧

May 16, 2016 pm 07:16 PM
排序演算法

具体代码及比较如下所示:

复制代码 代码如下:

nbsp;html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
 
 
 常见排序算法 之 JavaScript版  
 
 
 
<script> <BR> Array.prototype.swap = function(i, j) <BR> { <BR> var temp = this[i]; <BR> this[i] = this[j]; <BR> this[j] = temp; <BR> } <BR> Array.prototype.bubbleSort = function() <BR> { <BR> for (var i = this.length - 1; i > 0; --i) <BR> { <BR> for (var j = 0; j < i; ++j) <BR> { <BR> if (this[j] > this[j + 1]) this.swap(j, j + 1); <BR> } <BR> } <BR> } <BR> Array.prototype.selectionSort = function() <BR> { <BR> for (var i = 0; i < this.length; ++i) <BR> { <BR> var index = i; <BR> for (var j = i + 1; j < this.length; ++j) <BR> { <BR> if (this[j] < this[index]) index = j; <BR> } <BR> this.swap(i, index); <BR> } <BR> } <BR> Array.prototype.insertionSort = function() <BR> { <BR> for (var i = 1; i < this.length; ++i) <BR> { <BR> var j = i, value = this[i]; <BR> while (j > 0 && this[j - 1] > value) <BR> { <BR> this[j] = this[j - 1]; <BR> --j; <BR> } <BR> this[j] = value; <BR> } <BR> } <BR> Array.prototype.shellSort = function() <BR> { <BR> for (var step = this.length >> 1; step > 0; step >>= 1) <BR> { <BR> for (var i = 0; i < step; ++i) <BR> { <BR> for (var j = i + step; j < this.length; j += step) <BR> { <BR> var k = j, value = this[j]; <BR> while (k >= step && this[k - step] > value) <BR> { <BR> this[k] = this[k - step]; <BR> k -= step; <BR> } <BR> this[k] = value; <BR> } <BR> } <BR> } <BR> } <BR> Array.prototype.quickSort = function(s, e) <BR> { <BR> if (s == null) s = 0; <BR> if (e == null) e = this.length - 1; <BR> if (s >= e) return; <BR> this.swap((s + e) >> 1, e); <BR> var index = s - 1; <BR> for (var i = s; i <= e; ++i) <BR> { <BR> if (this[i] <= this[e]) this.swap(i, ++index); <BR> } <BR> this.quickSort(s, index - 1); <BR> this.quickSort(index + 1, e); <BR> } <BR> Array.prototype.stackQuickSort = function() <BR> { <BR> var stack = [0, this.length - 1]; <BR> while (stack.length > 0) <BR> { <BR> var e = stack.pop(), s = stack.pop(); <BR> if (s >= e) continue; <BR> this.swap((s + e) >> 1, e); <BR> var index = s - 1; <BR> for (var i = s; i <= e; ++i) <BR> { <BR> if (this[i] <= this[e]) this.swap(i, ++index); <BR> } <BR> stack.push(s, index - 1, index + 1, e); <BR> } <BR> } <BR> Array.prototype.mergeSort = function(s, e, b) <BR> { <BR> if (s == null) s = 0; <BR> if (e == null) e = this.length - 1; <BR> if (b == null) b = new Array(this.length); <BR> if (s >= e) return; <BR> var m = (s + e) >> 1; <BR> this.mergeSort(s, m, b); <BR> this.mergeSort(m + 1, e, b); <BR> for (var i = s, j = s, k = m + 1; i <= e; ++i) <BR> { <BR> b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; <BR> } <BR> for (var i = s; i <= e; ++i) this[i] = b[i]; <BR> } <BR> Array.prototype.heapSort = function() <BR> { <BR> for (var i = 1; i < this.length; ++i) <BR> { <BR> for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1) <BR> { <BR> if (this[k] >= this[j]) break; <BR> this.swap(j, k); <BR> } <BR> } <BR> for (var i = this.length - 1; i > 0; --i) <BR> { <BR> this.swap(0, i); <BR> for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) <BR> { <BR> if (k == i || this[k] < this[k - 1]) --k; <BR> if (this[k] <= this[j]) break; <BR> this.swap(j, k); <BR> } <BR> } <BR> } <BR> function generate() <BR> { <BR> var max = parseInt(txtMax.value), count = parseInt(txtCount.value); <BR> if (isNaN(max) || isNaN(count)) <BR> { <BR> alert("个数和最大值必须是一个整数"); <BR> return; <BR> } <BR> var array = []; <BR> for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max)); <BR> txtInput.value = array.join("\n"); <BR> txtOutput.value = ""; <BR> } <BR> function demo(type) <BR> { <BR> var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n"); <BR> for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]); <BR> var t1 = new Date(); <BR> eval("array." + type + "Sort()"); <BR> var t2 = new Date(); <BR> lblTime.innerText = t2.valueOf() - t1.valueOf(); <BR> txtOutput.value = array.join("\n"); <BR> } <BR></script> 
 
 
 
 
  
  
  
 
 
  
 
 
 随机数个数

 
 最大随机数

 
 



 
 耗时(毫秒):



 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 
  
 
 
 
 

快速排序, 插入排序, 希尔排序, 冒泡排序, quickSort, insertSort, shellSort, bubbleSort, javascript排序
说明
写这个主要是为了锻炼自己,并无实际意义。
每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快。
不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)
如果有兴趣可以 下载测试页面

个人理解

冒泡排序:最简单,也最慢,貌似长度小于7最优
插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势
快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合
希尔排序:在非chrome下数组长度小于1000,希尔排序比快速更快
系统方法:在forfox下系统的这个方法非常快

算法源码
复制代码 代码如下:

// ---------- 一些排序算法
// js 利用sort进行排序
systemSort:function(array){
return array.sort(function(a, b){
return a - b;
});
},
// 冒泡排序
bubbleSort:function(array){
var i = 0, len = array.length,
j, d;
for(; ifor(j=0; jif(array[i] 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){
// 结束条件
if(i == j ){ return };
var key = array[i];
var stepi = i; // 记录开始位置
var stepj = j; // 记录结束位置
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;
}
}
}
}
// 如果第一个取出的 key 是最小的数
if(stepi == i){
Sort(++i, stepj);
return ;
}
// 最后一个空位留给 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 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() 在维基上看到这个最优的步长 较小数组
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
// 排序一个步长
function stepSort(step){
//console.log(step) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;

for(;i for(j=1;/*j 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;
}

测试代码打包下载
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

快手雙邊市場的複雜實驗設計問題 快手雙邊市場的複雜實驗設計問題 Apr 15, 2023 pm 07:40 PM

一、問題背景1、雙邊市場實驗介紹雙邊市場,即平台,包含生產者與消費者兩方參與者,雙方相互促進。例如快手有影片的生產者,影片的消費者,兩種身分可能有一定程度重疊。雙邊實驗是在生產者和消費者端組合分組的實驗方式。雙邊實驗有以下優點:(1)可以同時偵測新策略對兩方面的影響,例如產品DAU和上傳作品人數變化。雙邊平台往往有跨邊網路效應,讀者越多,作者越活躍,作者越活躍,讀者也會跟著增加。 (2)可以檢測效果溢出和轉移。 (3)幫助我們更好得理解作用的機制,AB實驗本身不能告訴我們原因和結果之間的關係,只

Vue技術開發中如何進行資料篩選與排序 Vue技術開發中如何進行資料篩選與排序 Oct 09, 2023 pm 01:25 PM

Vue技術開發中如何進行資料篩選和排序在Vue技術開發中,資料篩選和排序是非常常見且重要的功能。透過資料篩選和排序,我們可以快速查詢和展示我們需要的信息,提高用戶體驗。本文將介紹在Vue中如何進行資料篩選和排序,並提供具體的程式碼範例,幫助讀者更好地理解和運用這些功能。一、資料篩選資料篩選是指依照特定的條件篩選出符合要求的資料。在Vue中,我們可以透過comp

谷歌借AI打破十年排序演算法封印,每天被執行數萬億次,網友卻說是最不切實際的研究? 谷歌借AI打破十年排序演算法封印,每天被執行數萬億次,網友卻說是最不切實際的研究? Jun 22, 2023 pm 09:18 PM

整理|核子可樂,褚杏娟接觸過基礎電腦科學課程的朋友們,肯定都曾親自動手設計排序演算法——也就是藉助代碼將無序列表中的各個條目按升序或降序方式重新排列。這是個有趣的挑戰,可行的操作方法也多元。人們曾投入大量時間探索如何更有效率地完成排序任務。作為一項基礎操作,大多數程式語言的標準庫中都內建有排序演算法。世界各地的程式碼庫中使用了許多不同的排序技術和演算法來在線組織大量數據,但至少就與LLVM編譯器配套使用的C++庫而言,排序程式碼已經有十多年沒有任何變化了。近日,GoogleDeepMindAI小組如今開發出一

如何使用C++中的基數排序演算法 如何使用C++中的基數排序演算法 Sep 19, 2023 pm 12:15 PM

如何使用C++中的基數排序演算法基數排序演算法是一種非比較性的排序演算法,它透過將待排序的元素分割成一組有限的數字位元來完成排序。在C++中,我們可以使用基數排序演算法來對一組整數進行排序。以下我們將詳細討論如何實作基數排序演算法,並附上具體的程式碼範例。演算法思想基數排序演算法的想法是將待排序的元素分割成一組有限的數字位,然後依序對每個位上的元素進行排序。在每個位元上的排序完

如何實作C#中的選擇排序演算法 如何實作C#中的選擇排序演算法 Sep 20, 2023 pm 01:33 PM

如何實現C#中的選擇排序演算法選擇排序(SelectionSort)是一種簡單直觀的排序演算法,其基本思想是每次從待排序元素中選擇最小(或最大)的元素,放到已排序的序列末尾。透過重複這個過程,直到所有元素都排序完成。下面我們來詳細了解如何在C#中實作選擇排序演算法,同時附上具體的程式碼範例。建立選擇排序方法首先,我們需要建立一個用於實作選擇排序的方法。此方法接受一

Swoole進階:如何使用多執行緒實作高速排序演算法 Swoole進階:如何使用多執行緒實作高速排序演算法 Jun 14, 2023 pm 09:16 PM

Swoole是一款基於PHP語言的高效能網路通訊框架,它支援多種非同步IO模式和多種高階網路協定的實作。在Swoole的基礎上,我們可以利用其多執行緒功能來實現高效率的演算法運算,例如高速排序演算法。高速排序演算法(QuickSort)是一種常見的排序演算法,透過定位一個基準元素,將元素分成兩個子序列,小於基準元素的放在左側,大於等於基準元素的放在右側,再對左右子序列遞迴

不同 PHP 數組排序演算法的應用場景探討 不同 PHP 數組排序演算法的應用場景探討 Apr 28, 2024 am 09:39 AM

針對不同場景,選擇合適的PHP數組排序演算法至關重要。冒泡排序適用於小規模數組無穩定性要求的情況;快速排序在大多數情況下時間複雜度最低;歸併排序穩定性高,適用於需要穩定結果的場景;選擇排序適用於無穩定性要求的情況;堆排序高效率找出最大或最小值。透過實戰案例比較,快速排序在時間效率上優於其他演算法,但需要考慮穩定性時應選擇歸併排序。

數組的排序演算法有哪些? 數組的排序演算法有哪些? Jun 02, 2024 pm 10:33 PM

數組排序演算法用於按特定順序排列元素。常見的演算法類型包括:冒泡排序:透過比較相鄰元素交換位置。選擇排序:找出最小元素交換到目前位置。插入排序:逐一插入元素到正確位置。快速排序:分治法,選擇樞紐元素劃分數組。合併排序:分治法,遞歸排序和合併子數組。

See all articles