Javascript_javascript 팁의 일반적인 정렬 알고리즘-JS 튜토리얼-php.cn

집

웹 프론트엔드

JS 튜토리얼

Javascript_javascript 팁의 일반적인 정렬 알고리즘

May 16, 2016 pm 07:16 PM

정렬 알고리즘

구체적인 코드와 비교는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다

<!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> 버전 </title> 
<meta http-equiv="content-type" content="text/html; charset=gb2312" /> 
<meta name="keywords" content=" , 알고리즘, JavaScript 정렬" /> 
<meta name="description" content="JavaScript에서 구현되는 일반적인 정렬 알고리즘: 버블 정렬, 선택 정렬, 삽입 정렬, Schell 정렬, 빠른 정렬(재귀), 빠른 정렬 (스택), 병합 정렬, 힙 정렬" /> 
<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  { 
 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; 단계 >>= 1) 
 { 
 for (var i = 0; i < step; i) 
 { 
 (var j = i 단계; j < this.length; j = 단계) 
 { 
 var k = j, value = this[j] 
 while (k >= 단계 && this[ k - 단계] > 값) 
 { 
 this[k] = this[k - 단계] 
 k -= 단계 
 } 
 this[k] = 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();  
 (s >= e) 계속되는 경우;  
 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 = 함수(s, e, b)  
 {  
 if (s == null) s = 0;  
 if (e == null) e = this.length - 1;  
 if (b == null) b = new Array(this.length);  
 (s >= e) 반환하는 경우;  
 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 &lt ;= m && 이[j] <  이[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)  
 {  
 (이것 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(최대) || isNaN(개수))  
 {  
 alert("个数和最大值必须是一个整数");  
 반품;  
 }  
 var 배열 = [];  
 for (var i = 0; i < count;  i) array.push(Math.round(Math.random() * max));  
 txtInput.value = array.join("n");  
 txtOutput.value = "";  
 }  
 함수 데모(유형)  
 {  
 var array = txtInput.value == "" ? [] : txtInput.value.replace().split("n");  
 for (var i = 0; i < array.length;  i) array[i] = parseInt(array[i]);  
 var t1 = 새 날짜();  
 eval("배열."   type   "정렬()");  
 var t2 = 새 날짜();  
 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;" 읽기 전용>  
 </td>  
 <td width="150" align="center">  
 随机数个数<input id="txtCount" value="500" style="width:50px" /><br /><br />  
 最大随机数<input id="txtMax" value="1000" style="width:50px" /><br /><br />  
 <button onclick="generate()">중신생성</button><br /><br /><br /><br />  
 耗时(毫秒)：<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;" 읽기 전용>  
 </td>  
</tr>  
</테이블>  
</body>  
</html> 

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

个人리解

冒泡排序：最简单，也最慢，貌似长島小于7最优 插入排序：比冒泡快，比快速排序화希尔排序慢，较小数据有优势
快速排序: 这是一个不常快的排序方式，V8 의 sort verb 1000，希尔排序比快速更快
系统方法：지금 forfox下系统的这个方법비常快

算法源码

复主代码代码如下:

 
// ---------- 일부 정렬 알고리즘 
// js는 정렬을 사용하여 정렬 
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 ] < 배열[j]){ 
d = 배열[j]; 
배열[j] = 배열[i] 
배열[i] = d 
 } 
} 
배열 반환 
}, 
//빠른 정렬
quickSort:function(array){ 
//var array = [8,4,6,2, 7 ,9,3,5,74,5]; 
//var 배열 = [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 }; 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; 
} 
} 
} 
// 추출된 키는 다음과 같습니다. 가장 작은 숫자 
if(stepi == i){ 
Sort( i, stepj); 
return ; 
} 
// 마지막 공간은 키 
 배열[ i] = key;// 재귀
Sort(stepi, i); 
Sort(j, stepj) 
} 
Sort(i, j); ; 
}, 
// 삽입 정렬 
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 , 단계, 키 , 
len = array.length; 
for(; i < len; i ){ 
step = j 
key = array[j] 
 while(-- j > -1){ 
if(array[j] > key){ 
array[j 1] = array[j] 
}else{ 
break; 
} 
array[j 1] = key; 
} 
return array; 
}, 
//Hill sort
//Jun.array .shellSort(Jun. array.df(10000)); 
shellSort:function(array){ 
// http://zh.wikipedia.org/zh/Hill sorting
// 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, 18 2 , 34, 9, 1]//대형 배열에 대한 단계 선택 
var i = 0; 
var stepArrLength = stepArr.length; 
var len = array.length; len/2); 
for(;i < stepArrLength; 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 ? parsInt(len/step) 1 : len/step; 

for(;i < step; i ) /순서대로 열 반복
for(j=1;/*j < stepLen && */step * j i < len j ){//순서대로 열 반복 각 열의 각 행
tem = f = step * j i; 
key = array[f]; 
while((tem-=step) >= 0){// 순서대로 위쪽으로 검색
if(array[tem ] > 키){ 
배열[항목 단계] = 배열[항목]; 
}else{ 
break; 
} 
} 
배열[ 항목 단계 ] = 키; 
} 
} 
} 
배열 반환 
} 



테스트 코드 패키지 다운로드