常见排序算法（JS版）

常见排序算法（JS版）包括：

　　内置排序,冒泡排序,选择排序,插入排序,希尔排序,快速排序（递归 & 堆栈）,归并排序,堆排序,以及分析每种排序算法的执行时间。

　　index.html

  1 <!DOCTYPE html>  
  2 <html>  
  3 <head>  
  4 <title>twobin 常见排序算法 （JS版） </title>  
  5 <meta http-equiv="content-type" content="text/html; charset=utf-8" />  
  6 <meta name="keywords" content="排序,算法,JavaScript排序" />  
  7 <meta name="description" content="常见排序算法:冒泡排序,选择排序,插入排序,希尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序" />
  8 <link rel="stylesheet" type="text/css" href="main.css" />
  9 <script type="text/javascript" src="main.js"></script>
 10 </head>  
 11 <body>  
 12 <div id="doc" class="y-t3">
 13     <div id="hd">
 14         <h1 class="h1">twobin 常见排序算法（JS版）</h1>
 15     </div>
 16     <div id="bd">
 17         <div class="y-main">
 18             <div class="y-g main">
 19                 <div>
 20                     <h2>随机生成乱序数组</h2>
 21                     <textarea id="txtInput" style="100%;height:100px;" readonly></textarea>
 22                     <h2>排序数组</h2>
 23                     <textarea id="txtOutput" style="100%;height:100px;" readonly></textarea>
 24                     <br /><br />
 25                     <div>            
 26                         <button id="btnSort">JS内置排序</button>  
 27                         <button id="btnBubble">冒泡排序</button>  
 28                         <button id="btnSelection" >选择排序</button> 
 29                         <button id="btnInsertion" >插入排序</button> 
 30                         <button id="btnShell" >希尔排序</button> 
 31                         <button id="btnQuick" >递归快速排序</button>  
 32                         <button id="btnStackQuick" >堆栈快速排序</button>  
 33                         <button id="btnMerge" >归并排序</button> 
 34                         <button id="btnHeap" >堆排序</button>
 35                         <button id="btnGenerate">生成随机数</button>
 36                         随机数个数：<input id="txtCount" value="10000" style="50px" /> 
 37                         最大随机数：<input id="txtMax" value="10000" style="50px" />              
 38                     </div>
 39                 </div>
 40                 <div>
 41                     <h2>排序算法性能</h2>
 42                     <table cellpadding="0" cellspacing="0" class="table bd_1">                       
 43                         <colgroup>
 44                             <col >
 45                             <col >
 46                             <col >
 47                         </colgroup>
 48                         <thead class="b f14">
 49                             <tr>
 50                                 <th class="tc">排序算法</th>
 51                                 <th class="tc">数组长度（个）</th>                                
 52                                 <th class="tc">平均耗时（毫秒）</th>                                                                    
 53                             </tr>
 54                         </thead>
 55                         <tbody id="memberListIn">   
 56                             <tr id="970000000000001">
 57                                 <td  class="tc">JS内置排序</td>
 58                                 <td><span id="length_1"></span></td>
 59                                 <td><span id="time_1"></span></td>
 60                             </tr>
 61                             <tr id="970000000000001">
 62                                 <td  class="tc">冒泡排序</td>
 63                                 <td><span id="length_2"></span></td>
 64                                 <td><span id="time_2"></span></td>
 65                             </tr>
 66                             <tr id="970000000000001">
 67                                 <td  class="tc">选择排序</td>
 68                                 <td><span id="length_3"></span></td>
 69                                 <td><span id="time_3"></span></td>
 70                             </tr>
 71                             <tr id="970000000000001">
 72                                 <td  class="tc">插入排序</td>
 73                                 <td><span id="length_4"></span></td>
 74                                 <td><span id="time_4"></span></td>
 75                             </tr>
 76                             <tr id="970000000000001">
 77                                 <td  class="tc">希尔排序</td>
 78                                 <td><span id="length_5"></span></td>
 79                                 <td><span id="time_5"></span></td>
 80                             </tr>
 81                             <tr id="970000000000001">
 82                                 <td  class="tc">递归快速排序</td>
 83                                 <td><span id="length_6"></span></td>
 84                                 <td><span id="time_6"></span></td>
 85                             </tr>
 86                             <tr id="970000000000001">
 87                                 <td  class="tc">堆栈快速排序</td>
 88                                 <td><span id="length_7"></span></td>
 89                                 <td><span id="time_7"></span></td>
 90                             </tr>
 91                             <tr id="970000000000001">
 92                                 <td  class="tc">归并排序</td>
 93                                 <td><span id="length_8"></span></td>
 94                                 <td><span id="time_8"></span></td>
 95                             </tr>
 96                             <tr id="970000000000001">
 97                                 <td  class="tc">堆排序</td>
 98                                 <td><span id="length_9"></span></td>
 99                                 <td><span id="time_9"></span></td>
100                             </tr>
101                         </tbody>
102                     </table>
103                 </div>
104             </div>
105         </div>
106     </div>
107 </div>
108 </body>  
109 </html>

main.js

 1 /* yahoo reset */
 2 html{color:#000;background:#FFF;}
 3 body,div,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,code,form,fieldset,legend,input,textarea,p,blockquote,th,td{margin:0;padding:0;}table{border-collapse:collapse;border-spacing:0;}fieldset,img{border:0;}address,caption,cite,code,dfn,em,strong,th,var{font-style:normal;font-weight:normal;}li{list-style:none;}caption,th{text-align:left;}h1,h2,h3,h4,h5,h6{font-size:100%;font-weight:normal;}q:before,q:after{content:'';}abbr,acronym {border:0;font-variant:normal;}sup {vertical-align:text-top;}sub {vertical-align:text-bottom;}input,textarea,select{font-family:inherit;font-size:inherit;font-weight:inherit;}input,textarea,select{*font-size:100%;}legend{color:#000;}body {font:13px/1.231 arial,helvetica,clean,sans-serif;*font-size:small;*font:x-small;}table {font-size:inherit;font:100%;}pre,code,kbd,samp,tt{font-family:monospace;*font-size:108%;line-height:100%;}
 4 
 5 /* 必须 */
 6 body{font:13px/1.231 arial,helvetica,clean,sans-serif; text-align:center;}
 7 #doc{margin:0 auto; text-align:left;}    
 8 #doc{width:100%;}/* 网页宽度*/
 9 
10 .y-main{width:100%;}    
11 .y-b{width:180px;} /* 侧栏宽度 */    
12 .y-u{width:49.3%;float:right;}
13 .first{float:left;}
14 
15 .y-t1 .y-b{float:right;}
16 .y-t1 .y-main{float:left;margin-right:-190px;}
17 .y-t1 .y-main .y-g{margin-right:190px;}
18 
19 .y-t2 .y-b{float:left;}
20 .y-t2 .y-main{float:right;margin-left:-190px;}
21 .y-t2 .y-main .y-g{margin-left:190px;}
22 
23 .y-t3 .y-b{float:left; display:none;}
24 .y-t3 .y-main{float:right;margin-left:-190px;}
25 .y-t3 .y-main .y-g{margin-left:0;}
26 
27 #bd,#hd,.clear{*zoom:1;}
28 #bd:after,.clear:after{content:"20";display:block;height:0;clear:both;visibility:hidden;}    
29 /*以上必须*/
30 
31 /**/
32 .y-b{ display:none;}
33 #hd,#fd{ height:50px; background:#f8f8f8;}
34 #hd{border-bottom:1px solid #ccc; overflow:hidden;}
35 #fd{border-top:1px solid #ccc;}
36 .h1{font-size:24px; margin:10px 0 0 30px;}
37 .main{padding:20px;}    
38 .main h2{ font-size:18px; font-weight:700; margin:5px 0;}
39 
40 /*member*/
41 .b{ font-weight:700;}
42 .bd_1{border:1px solid #ABB8CE;}
43 .f14{ font-size:14px;}
44 .tc{ text-align:center;}
45 .tl{ text-align:left;}
46 
47 .table_list{}
48 .w30{ width:30px;}
49 .w50{ width:50px;}
50 .w100{ width:100px;}
51 .table_list .menu,.menu .page_number{padding:6px 8px 4px 8px; }
52 .table_list .menu{background:#E3E5E6;position:relative;}
53 .menu .page_number{ display:inline-block; position:absolute; right:0; top:5px;+margin-right:20px;}
54 .menu .m_r10{_margin-left:-4px;}
55 button{width: 100px;height: 30px;}
56 
57 .table{cellpadding:0;cellspacing:0; width:100%;line-height:2.5em; font-size:12px; text-align:center;}
58 .table thead{ border-bottom:1px solid #FFF;}
59 .table thead,.table tr:hover,.js_hover{background:#D0DBEE;}
60 .table thead th{font-weight:700;}
61 .table .even{background:#EEF4F7;}

main.js

  1 window.onload=function(){
  2     //生成随机数
  3     generate();
  4     var oGenerate=document.getElementById('btnGenerate');
  5     var oSort=document.getElementById('btnSort');
  6     var oBubble=document.getElementById('btnBubble');
  7     var oSelection=document.getElementById('btnSelection');
  8     var oInsertion=document.getElementById('btnInsertion');
  9     var oShell=document.getElementById('btnShell');
 10     var oQuick=document.getElementById('btnQuick');
 11     var oStackQuick=document.getElementById('btnStackQuick');
 12     var oMerge=document.getElementById('btnMerge');
 13     var oHeap=document.getElementById('btnHeap');
 14     var oTxtCount=document.getElementById('txtCount');
 15     
 16     oGenerate.onclick=function(){
 17         generate();
 18     }
 19     oSort.onclick=function(){
 20         document.getElementById('time_1').innerText=sortAlgorithm('js');
 21         document.getElementById('length_1').innerText=oTxtCount.value;
 22     }
 23     oBubble.onclick=function(){
 24         document.getElementById('time_2').innerText=sortAlgorithm('bubble');
 25         document.getElementById('length_2').innerText=oTxtCount.value;
 26     }
 27     oSelection.onclick=function(){
 28         document.getElementById('time_3').innerText=sortAlgorithm('selection');
 29         document.getElementById('length_3').innerText=oTxtCount.value;
 30     }
 31     oInsertion.onclick=function(){
 32         document.getElementById('time_4').innerText=sortAlgorithm('insertion');
 33         document.getElementById('length_4').innerText=oTxtCount.value;
 34     }
 35     oShell.onclick=function(){
 36         document.getElementById('time_5').innerText=sortAlgorithm('shell');
 37         document.getElementById('length_5').innerText=oTxtCount.value;
 38     }
 39     oQuick.onclick=function(){
 40         document.getElementById('time_6').innerText=sortAlgorithm('quick');
 41         document.getElementById('length_6').innerText=oTxtCount.value;
 42     }
 43     oStackQuick.onclick=function(){
 44         document.getElementById('time_7').innerText=sortAlgorithm('stackQuick');
 45         document.getElementById('length_7').innerText=oTxtCount.value;
 46     }
 47     oMerge.onclick=function(){
 48         document.getElementById('time_8').innerText=sortAlgorithm('merge');
 49         document.getElementById('length_8').innerText=oTxtCount.value;
 50     }
 51     oHeap.onclick=function(){
 52         document.getElementById('time_9').innerText=sortAlgorithm('heap');
 53         document.getElementById('length_9').innerText=oTxtCount.value;
 54     }
 55 };
 56 //交换函数
 57 Array.prototype.swap = function(i, j) {  
 58     var temp = this[i];  
 59     this[i] = this[j];  
 60     this[j] = temp;  
 61 }  
 62 //JS内置排序
 63 Array.prototype.jsSort = function() {   
 64     return this.sort(function(a, b){
 65             return a - b;
 66         });
 67 }  
 68 //冒泡排序
 69 Array.prototype.bubbleSort = function() {  
 70     for (var i = this.length - 1; i > 0; --i)  
 71     {  
 72         for (var j = 0; j < i; ++j)  
 73             if (this[j] > this[j + 1]) 
 74                 this.swap(j, j + 1);  
 75     }  
 76 }  
 77 //选择排序
 78 Array.prototype.selectionSort = function() {  
 79     for (var i = 0; i < this.length; ++i)  
 80     {  
 81         var index = i;  
 82         for (var j = i + 1; j < this.length; ++j)  
 83         {  
 84             if (this[j] < this[index]) 
 85                 index = j;  
 86         }  
 87         this.swap(i, index);  
 88     }  
 89 }  
 90 //插入排序
 91 Array.prototype.insertionSort = function() {  
 92     for (var i = 1; i < this.length; ++i)  
 93     {  
 94         var j = i, 
 95             value = this[i];  
 96         while (j > 0 && this[j - 1] > value)  
 97         {  
 98             this[j] = this[j - 1];  
 99             --j;  
100         }  
101         this[j] = value;  
102     }  
103 }  
104 //希尔排序(>>位运算)
105 Array.prototype.shellSort = function() {  
106     for (var step = this.length >> 1; step > 0; step >>= 1)  
107     {  
108         //alert(step >>= 1);
109         for (var i = 0; i < step; ++i)  
110         {  
111             for (var j = i + step; j < this.length; j += step)  
112             {  
113                 var k = j, value = this[j];  
114                 while (k >= step && this[k - step] > value)  
115                 {  
116                     this[k] = this[k - step];  
117                     k -= step;  
118                 }  
119                 this[k] = value;  
120             }  
121         }  
122     }  
123 }  
124 //递归快速排序
125 Array.prototype.quickSort = function(s, e) {  
126     if (s == null) 
127         s = 0;  
128     if (e == null) 
129         e = this.length - 1;  
130     if (s >= e) 
131         return;  
132     this.swap((s + e) >> 1, e);  
133     var index = s - 1;  
134     for (var i = s; i <= e; ++i)   
135         if (this[i] <= this[e]) this.swap(i, ++index);  
136     this.quickSort(s, index - 1);  
137     this.quickSort(index + 1, e);  
138 }  
139 //堆栈快速排序
140 Array.prototype.stackQuickSort = function() {  
141     var stack = [0, this.length - 1];  
142     while (stack.length > 0)  
143     {  
144         var e = stack.pop(), s = stack.pop();  
145         if (s >= e) 
146             continue;  
147         this.swap((s + e) >> 1, e);  
148         var index = s - 1;  
149         for (var i = s; i <= e; ++i)  
150         {  
151             if (this[i] <= this[e]) 
152             this.swap(i, ++index);  
153         }  
154         stack.push(s, index - 1, index + 1, e);  
155     }  
156 }  
157 //归并排序
158 Array.prototype.mergeSort = function(s, e, b) {  
159     if (s == null) 
160         s = 0;  
161     if (e == null) 
162         e = this.length - 1;  
163     if (b == null) 
164         b = new Array(this.length);  
165     if (s >= e) 
166         return;  
167     var m = (s + e) >> 1;  
168     this.mergeSort(s, m, b);  
169     this.mergeSort(m + 1, e, b);  
170     for (var i = s, j = s, k = m + 1; i <= e; ++i)   
171         b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++];  
172     for (var i = s; i <= e; ++i) 
173         this[i] = b[i];  
174 }  
175 //堆排序
176 Array.prototype.heapSort = function() {  
177     for (var i = 1; i < this.length; ++i)  
178         {  
179         for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1)  
180         {  
181             if (this[k] >= this[j]) 
182                 break;  
183             this.swap(j, k);  
184         }  
185     }  
186     for (var i = this.length - 1; i > 0; --i)  
187     {  
188         this.swap(0, i);  
189         for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1)  
190         {  
191             if (k == i || this[k] < this[k - 1]) 
192                 --k;  
193             if (this[k] <= this[j]) 
194                 break;  
195             this.swap(j, k);  
196         }  
197     }  
198 }  
199 //生成随机数
200 function generate() {  
201     var max = parseInt(txtMax.value), 
202         count = parseInt(txtCount.value);  
203     if (isNaN(max) || isNaN(count))  
204     {  
205         alert("随机数个数和最大值必须是整数");  
206         return;  
207     }  
208     var array = [];  
209     for (var i = 0; i < count; ++i) 
210         array.push(Math.round(Math.random() * max));  
211     txtInput.value = array.join(",");  
212     txtOutput.value = "";  
213 }  
214 //返回排序时间
215 function sortAlgorithm(type) {  
216     var timer=0;
217     var array = txtInput.value == "" ? [] : txtInput.value.replace().split(",");  
218     for (var i = 0; i < array.length; ++i) 
219         array[i] = parseInt(array[i]);  
220     var t1 = new Date(); 
221     //eval() 函数可计算某个字符串，并执行其中的的JavaScript代码 
222     eval("array." + type + "Sort()");  
223     var t2 = new Date();  
224     timer= t2.valueOf() - t1.valueOf();  
225     txtOutput.value = array.join(",");  
226     return timer;
227 }

排序效果：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jiechen/p/5470416.html