快速排序（Quicksort）是對冒泡排序的一種改進。快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以 ...
快速排序（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>View Code
快速排序演算法，優化方案：
- 三平均分區法，將待排序的數據分為前，中，後 三個區
- 根據分區大小調整演算法，因為快速排序演算法對於數據較少時並沒有優勢
- 並行的分區快速排序，由於快速排序演算法是採用分治技術來進行實現的，這就使得它很容易能夠在多台處理機上並行處理。
