首页 > 代码库 > Html5 快速排序演示
Html5 快速排序演示
快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。
- 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
- 每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。
- 快速排序的平均运行时间为O(nlogn)。
-----------------------------------------------------------------------------------------------------------------------------------------
演示如下图所示：
算法原理不再赘述，具体代码如下：
1 <!DOCTYPE html> 2 <html> 3 <head> 4 <title>The twelve html page</title> 5 <style type="text/css"> 6 ul li 7 { 8 list-style-type:georgian; 9 text-align:left; 10 } 11 .mark 12 { 13 width:180px; 14 height:40px; 15 color:Olive; 16 text-align:center; 17 line-height:40px; 18 margin:5px; 19 float:left; 20 } 21 .redball 22 { 23 width:40px; 24 height:40px; 25 border-radius:20px; 26 background-color:Red; 27 text-align:center; 28 line-height:40px; 29 margin:5px; 30 float:left; 31 } 32 .ball 33 { 34 width:40px; 35 height:40px; 36 border-radius:20px; 37 background-color:Aqua; 38 text-align:center; 39 line-height:40px; 40 margin:5px; 41 float:left; 42 } 43 .line 44 { 45 clear:left; 46 } 47 header 48 { 49 height:80px; 50 border:1px solid gray; 51 } 52 .left 53 { 54 border:1px solid gray; 55 float:left; 56 width:30%; 57 height:480px; 58 margin-left:0px; 59 margin-right:0px; 60 61 } 62 aside 63 { 64 text-align:center; 65 } 66 section 67 { 68 width:69.5%; 69 float:left; 70 height:480px; 71 border:1px solid gray; 72 margin-left:0px; 73 margin-right:0px; 74 } 75 footer 76 { 77 clear:left; 78 height:60px; 79 border:1px solid gray; 80 } 81 input[type="button"] 82 { 83 width:80px; 84 text-align:center; 85 margin-top:10px; 86 } 87 </style> 88 <script type="text/javascript"> 89 function initDiv() { 90 var mainArea = document.getElementById("mainArea"); 91 for (var i = 0; i < 8; i++) { 92 var newDivLine = document.createElement("div"); 93 newDivLine.setAttribute("class", "line"); 94 mainArea.appendChild(newDivLine); 95 for (var j = 0; j < 9; j++) { 96 var newDiv = document.createElement("div"); 97 var id = i.toString() + j.toString(); 98 newDiv.setAttribute("id", id); 99 if (j < 8) { 100 newDiv.setAttribute("class", "ball"); 101 } else { 102 newDiv.setAttribute("class", "mark"); 103 } 104 newDivLine.appendChild(newDiv); 105 } 106 } 107 } 108 109 function setElementsValue() { 110 var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1];//初始元素赋值 111 for (var i = 0; i < arrTmp.length; i++) { 112 document.getElementById("0" + i.toString()).innerText = arrTmp[i]; 113 } 114 document.getElementById("08").innerText = "原始数据"; 115 } 116 var m = 0; //表示第几趟排序 117 //快速排序 118 function setQuickSortValue() { 119 m = 0; 120 var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; 121 QuickSort(arrTmp,0,arrTmp.length-1); 122 } 123 function QuickSort(arrTmp, low, high) { 124 if (low >= high) { 125 return; 126 } 127 //完成一次单元排序 128 var index = QuickSortUnit(arrTmp, low, high); 129 130 //对左边进行排序 131 QuickSort(arrTmp, low, index - 1); 132 //对右边进行排序 133 QuickSort(arrTmp, index + 1, high); 134 } 135 136 //快速排序单元 137 function QuickSortUnit(arrTmp, low, high) { 138 var key = arrTmp[low]; 139 while (low < high) { 140 //从后向前搜索比key小的值 141 while (arrTmp[high] >= key && high > low) { 142 --high; 143 } 144 //比key小的放左边 145 arrTmp[low] = arrTmp[high]; 146 while (arrTmp[low] <= key && high > low) { 147 ++low; 148 } 149 arrTmp[high] = arrTmp[low]; 150 } 151 arrTmp[low] = key; 152 m = m + 1; 153 ShowHtml(arrTmp, m, high); 154 return high; 155 } 156 157 //m表示第几趟排序，index表示分组的分界线 158 function ShowHtml(arrTmp,m,index) { 159 //显示出来 160 for (var k = 0; k < arrTmp.length; k++) { 161 document.getElementById((m).toString() + k.toString()).innerText = arrTmp[k]; 162 if (index == k) { 163 document.getElementById((m).toString() + (k).toString()).setAttribute("class", "redball"); 164 } 165 } 166 document.getElementById((m).toString() + "8").innerText += "第 " + (m).toString() + " 趟排序(index="+index+")"; 167 } 168 169 </script> 170 </head> 171 <body> 172 <header> 173 <h1>快速排序(Quick Sort)Demo</h1> 174 </header> 175 <aside class="left"> 176 177 <input type="button" id="btnInit" value="Init" onclick="initDiv();" /> 178 <br /> 179 <input type="button" id="btnSetValue" value="SetValue" onclick="setElementsValue();" /> 180 <br /> 181 <input type="button" id="btnSort" value="Quick Sort" onclick="setQuickSortValue();" /> 182 <br /> 183 <h3>快速排序(Quick Sort)</h3> 184 <ul> 185 <li>快速排序（Quicksort）是对冒泡排序的一种改进。<mark>交换排序</mark></li> 186 <li>快速排序是<mark>非稳定</mark>排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。</li> 187 <li>基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以<mark>递归</mark>进行，以此达到整个数据变成有序序列。</li> 188 <li>设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。</li> 189 <li>快速排序的平均运行时间为O(nlogn)。</li> 190 </ul> 191 </aside> 192 <section id="mainArea"> 193 194 </section> 195 <footer> 196 这是底部信息 197 </footer> 198 </body> 199 </html>
快速排序算法，优化方案：
- 三平均分区法，将待排序的数据分为前，中，后 三个区
- 根据分区大小调整算法，因为快速排序算法对于数据较少时并没有优势
- 并行的分区快速排序，由于快速排序算法是采用分治技术来进行实现的，这就使得它很容易能够在多台处理机上并行处理。
Html5 快速排序演示
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。