Skip to main content
 首页 » 编程设计

JS常见排序算法

2022年07月16日30freeliver54
  1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
  2 <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312"> 
  3 <head> 
  4     <title> 常见排序算法 之 JavaScript版 </title> 
  5     <meta http-equiv="content-type" content="text/html; charset=gb2312" /> 
  6     <meta name="keywords" content="排序,算法,JavaScript排序" /> 
  7     <meta name="description" content="用JavaScript实现的常见排序算法:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序" /> 
  8     <script type="text/javascript"> 
  9         Array.prototype.swap = function(i, j) 
 10         { 
 11             var temp = this[i]; 
 12             this[i] = this[j]; 
 13             this[j] = temp; 
 14         } 
 15         Array.prototype.bubbleSort = function() 
 16         { 
 17             for (var i = this.length - 1; i > 0; --i) 
 18             { 
 19                 for (var j = 0; j < i; ++j) 
 20                 { 
 21                     if (this[j] > this[j + 1]) this.swap(j, j + 1); 
 22                 } 
 23             } 
 24         } 
 25         Array.prototype.selectionSort = function() 
 26         { 
 27             for (var i = 0; i < this.length; ++i) 
 28             { 
 29                 var index = i; 
 30                 for (var j = i + 1; j < this.length; ++j) 
 31                 { 
 32                     if (this[j] < this[index]) index = j; 
 33                 } 
 34                 this.swap(i, index); 
 35             } 
 36         } 
 37         Array.prototype.insertionSort = function() 
 38         { 
 39             for (var i = 1; i < this.length; ++i) 
 40             { 
 41                 var j = i, value = this[i]; 
 42                 while (j > 0 && this[j - 1] > value) 
 43                 { 
 44                     this[j] = this[j - 1]; 
 45                     --j; 
 46                 } 
 47                 this[j] = value; 
 48             } 
 49         } 
 50         Array.prototype.shellSort = function() 
 51         { 
 52             for (var step = this.length >> 1; step > 0; step >>= 1) 
 53             { 
 54                 for (var i = 0; i < step; ++i) 
 55                 { 
 56                     for (var j = i + step; j < this.length; j += step) 
 57                     { 
 58                         var k = j, value = this[j]; 
 59                         while (k >= step && this[k - step] > value) 
 60                         { 
 61                             this[k] = this[k - step]; 
 62                             k -= step; 
 63                         } 
 64                         this[k] = value; 
 65                     } 
 66                 } 
 67             } 
 68         } 
 69         Array.prototype.quickSort = function(s, e) 
 70         { 
 71             if (s == null) s = 0; 
 72             if (e == null) e = this.length - 1; 
 73             if (s >= e) return; 
 74             this.swap((s + e) >> 1, e); 
 75             var index = s - 1; 
 76             for (var i = s; i <= e; ++i) 
 77             { 
 78                 if (this[i] <= this[e]) this.swap(i, ++index); 
 79             } 
 80             this.quickSort(s, index - 1); 
 81             this.quickSort(index + 1, e); 
 82         } 
 83         Array.prototype.stackQuickSort = function() 
 84         { 
 85             var stack = [0, this.length - 1]; 
 86             while (stack.length > 0) 
 87             { 
 88                 var e = stack.pop(), s = stack.pop(); 
 89                 if (s >= e) continue; 
 90                 this.swap((s + e) >> 1, e); 
 91                 var index = s - 1; 
 92                 for (var i = s; i <= e; ++i) 
 93                 { 
 94                     if (this[i] <= this[e]) this.swap(i, ++index); 
 95                 } 
 96                 stack.push(s, index - 1, index + 1, e); 
 97             } 
 98         } 
 99         Array.prototype.mergeSort = function(s, e, b) 
100         { 
101             if (s == null) s = 0; 
102             if (e == null) e = this.length - 1; 
103             if (b == null) b = new Array(this.length); 
104             if (s >= e) return; 
105             var m = (s + e) >> 1; 
106             this.mergeSort(s, m, b); 
107             this.mergeSort(m + 1, e, b); 
108             for (var i = s, j = s, k = m + 1; i <= e; ++i) 
109             { 
110                 b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; 
111             } 
112             for (var i = s; i <= e; ++i) this[i] = b[i]; 
113         } 
114         Array.prototype.heapSort = function() 
115         { 
116             for (var i = 1; i < this.length; ++i) 
117             { 
118                 for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1) 
119                 { 
120                     if (this[k] >= this[j]) break; 
121                     this.swap(j, k); 
122                 } 
123             } 
124             for (var i = this.length - 1; i > 0; --i) 
125             { 
126                 this.swap(0, i); 
127                 for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) 
128                 { 
129                     if (k == i || this[k] < this[k - 1]) --k; 
130                     if (this[k] <= this[j]) break; 
131                     this.swap(j, k); 
132                 } 
133             } 
134         } 
135         function generate() 
136         { 
137             var max = parseInt(txtMax.value), count = parseInt(txtCount.value); 
138             if (isNaN(max) || isNaN(count)) 
139             { 
140                 alert("个数和最大值必须是一个整数"); 
141                 return; 
142             } 
143             var array = []; 
144             for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max)); 
145             txtInput.value = array.join("\n"); 
146             txtOutput.value = ""; 
147         } 
148         function demo(type) 
149         { 
150             var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n"); 
151             for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]); 
152             var t1 = new Date(); 
153             eval("array." + type + "Sort()"); 
154             var t2 = new Date(); 
155             lblTime.innerText = t2.valueOf() - t1.valueOf(); 
156             txtOutput.value = array.join("\n"); 
157         } 
158  
159     </script> 
160 </head> 
161 <body onload="generate();"> 
162 <table style="font-size:12px;"> 
163     <tr> 
164         <td align="right"> 
165             <textarea id="txtInput" style="width:120px;height:500px;" readonly></textarea> 
166         </td> 
167         <td width="150" align="center"> 
168             随机数个数<input id="txtCount" value="500" style="width:50px" /><br /><br /> 
169             最大随机数<input id="txtMax" value="1000" style="width:50px" /><br /><br /> 
170             <button onclick="generate()">重新生成</button><br /><br /><br /><br /> 
171             耗时(毫秒):<label id="lblTime"></label><br /><br /><br /><br /> 
172             <button onclick="demo('bubble');">冒泡排序</button><br /><br /> 
173             <button onclick="demo('selection');">选择排序</button><br /><br /> 
174             <button onclick="demo('insertion');">插入排序</button><br /><br /> 
175             <button onclick="demo('shell');">谢尔排序</button><br /><br /> 
176             <button onclick="demo('quick');">快速排序(递归)</button><br /><br /> 
177             <button onclick="demo('stackQuick');">快速排序(堆栈)</button><br /><br /> 
178             <button onclick="demo('merge');">归并排序</button><br /><br /> 
179             <button onclick="demo('heap');">堆排序</button><br /><br /> 
180         </td> 
181         <td align="left"> 
182             <textarea id="txtOutput" style="width:120px;height:500px;" readonly></textarea> 
183         </td> 
184     </tr> 
185 </table> 
186 </body> 
187 </html> 
View Code

本文参考链接:https://www.cnblogs.com/webFrontDev/p/3317395.html