快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。
- 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
- 每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。
- 快速排序的平均运行时间为O(nlogn)。
—————————————————————————————————————————————–
演示如下图所示：
算法原理不再赘述，具体代码如下：
<!DOCTYPE html> <html> <head> <title>The twelve html page</title> <style type="text/css"> ul li { list-style-type:georgian; text-align:left; } .mark { width:180px; height:40px; color:Olive; text-align:center; line-height:40px; margin:5px; float:left; } .redball { width:40px; height:40px; border-radius:20px; background-color:Red; text-align:center; line-height:40px; margin:5px; float:left; } .ball { width:40px; height:40px; border-radius:20px; background-color:Aqua; text-align:center; line-height:40px; margin:5px; float:left; } .line { clear:left; } header { height:80px; border:1px solid gray; } .left { border:1px solid gray; float:left; width:30%; height:480px; margin-left:0px; margin-right:0px; } aside { text-align:center; } section { width:69.5%; float:left; height:480px; border:1px solid gray; margin-left:0px; margin-right:0px; } footer { clear:left; height:60px; border:1px solid gray; } input[type="button"] { width:80px; text-align:center; margin-top:10px; } </style> <script type="text/javascript"> function initDiv() { var mainArea = document.getElementById("mainArea"); for (var i = 0; i < 8; i++) { var newDivLine = document.createElement("div"); newDivLine.setAttribute("class", "line"); mainArea.appendChild(newDivLine); for (var j = 0; j < 9; j++) { var newDiv = document.createElement("div"); var id = i.toString() + j.toString(); newDiv.setAttribute("id", id); if (j < 8) { newDiv.setAttribute("class", "ball"); } else { newDiv.setAttribute("class", "mark"); } newDivLine.appendChild(newDiv); } } } function setElementsValue() { var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1];//初始元素赋值 for (var i = 0; i < arrTmp.length; i++) { document.getElementById("0" + i.toString()).innerText = arrTmp[i]; } document.getElementById("08").innerText = "原始数据"; } var m = 0; //表示第几趟排序 //快速排序 function setQuickSortValue() { m = 0; var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; QuickSort(arrTmp,0,arrTmp.length-1); } function QuickSort(arrTmp, low, high) { if (low >= high) { return; } //完成一次单元排序 var index = QuickSortUnit(arrTmp, low, high); //对左边进行排序 QuickSort(arrTmp, low, index - 1); //对右边进行排序 QuickSort(arrTmp, index + 1, high); } //快速排序单元 function QuickSortUnit(arrTmp, low, high) { var key = arrTmp[low]; while (low < high) { //从后向前搜索比key小的值 while (arrTmp[high] >= key && high > low) { --high; } //比key小的放左边 arrTmp[low] = arrTmp[high]; while (arrTmp[low] <= key && high > low) { ++low; } arrTmp[high] = arrTmp[low]; } arrTmp[low] = key; m = m + 1; ShowHtml(arrTmp, m, high); return high; } //m表示第几趟排序，index表示分组的分界线 function ShowHtml(arrTmp,m,index) { //显示出来 for (var k = 0; k < arrTmp.length; k++) { document.getElementById((m).toString() + k.toString()).innerText = arrTmp[k]; if (index == k) { document.getElementById((m).toString() + (k).toString()).setAttribute("class", "redball"); } } document.getElementById((m).toString() + "8").innerText += "第 " + (m).toString() + " 趟排序(index="+index+")"; } </script> </head> <body> <header> <h1>快速排序(Quick Sort)Demo</h1> </header> <aside class="left"> <input type="button" id="btnInit" value="Init" onclick="initDiv();" /> <br /> <input type="button" id="btnSetValue" value="SetValue" onclick="setElementsValue();" /> <br /> <input type="button" id="btnSort" value="Quick Sort" onclick="setQuickSortValue();" /> <br /> <h3>快速排序(Quick Sort)</h3> <ul> <li>快速排序（Quicksort）是对冒泡排序的一种改进。<mark>交换排序</mark></li> <li>快速排序是<mark>非稳定</mark>排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。</li> <li>基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以<mark>递归</mark>进行，以此达到整个数据变成有序序列。</li> <li>设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。</li> <li>快速排序的平均运行时间为O(nlogn)。</li> </ul> </aside> <section id="mainArea"> </section> <footer> 这是底部信息 </footer> </body> </html>
快速排序算法，优化方案：
- 三平均分区法，将待排序的数据分为前，中，后 三个区
- 根据分区大小调整算法，因为快速排序算法对于数据较少时并没有优势
- 并行的分区快速排序，由于快速排序算法是采用分治技术来进行实现的，这就使得它很容易能够在多台处理机上并行处理。
