快速排序(Quicksort)的Javascript实现

openkk 9年前
     <p><a href="/misc/goto?guid=4959499982822886310" target="_blank">排序算法</a>(Sorting algorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员,就必须理解和掌握各种排序算法。</p>    <p>目前,最常见的排序算法大概有七八种,其中<a href="/misc/goto?guid=4958201848898154185" target="_blank">"快速排序"</a>(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。</p>    <p>"快速排序"的思想很简单,整个排序过程只需要三步:</p>    <blockquote>     <p>(1)在数据集之中,选择一个元素作为"基准"(pivot)。</p>     <p>(2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。</p>     <p>(3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。</p>    </blockquote>    <p>举例来说,现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50},怎么对其排序呢?</p>    <p>第一步,选择中间的元素45作为"基准"。(基准值可以任意选择,但是选择中间的值比较容易理解。)</p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/22389c5582e3dcc1ab7e16bb3efcce9e.jpg" /></p>    <p>第二步,按照顺序,将每个元素与"基准"进行比较,形成两个子集,一个"小于45",另一个"大于等于45"。</p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/3e66859cfb5e5ad9211b008053a7d449.jpg" /></p>    <p>第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。</p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/b8cad5e16f5cb33d60753abde46505af.jpg" /></p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/a70aa18339a96c5959d60501d794c9ad.jpg" /></p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/84ae45b57ae3f2d1da3413872e0d66ad.jpg" /></p>    <p data-mce-=""><img alt="" src="https://simg.open-open.com/show/ae550197edc6ea3611df20b1e2473ef4.jpg" /></p>    <p>下面参照网上的资料(<a href="/misc/goto?guid=4959499983063784460" target="_blank">这里</a>和<a href="/misc/goto?guid=4959499983253382417" target="_blank">这里</a>),用Javascript语言实现上面的算法。</p>    <p>首先,定义一个quickSort函数,它的参数是一个数组。</p>    <div class="cnblogs_code">     <pre><span style="color:#0000ff;">var</span> quickSort = <span style="color:#0000ff;">function</span>(arr) { };</pre>    </div>    <p><span>然后,检查数组的元素个数,如果小于等于1,就返回。</span></p>    <div class="cnblogs_code">     <pre><span style="color:#0000ff;">var</span> quickSort = <span style="color:#0000ff;">function</span>(arr) {   <span style="color:#0000ff;">if</span> (arr.length <= 1) { <span style="color:#0000ff;">return</span> arr; } };</pre>    </div>    <p><span>接着,选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。</span></p>    <div class="cnblogs_code">     <pre><span style="color:#0000ff;">var</span> quickSort = <span style="color:#0000ff;">function</span>(arr) {   <span style="color:#0000ff;">if</span> (arr.length <= 1) { <span style="color:#0000ff;">return</span> arr; }   <span style="color:#0000ff;">var</span> pivotIndex = Math.floor(arr.length / 2) ;   <span style="color:#0000ff;">var</span> pivot = arr.splice(pivotIndex, 1)[0];   <span style="color:#0000ff;">var</span> left = [];   <span style="color:#0000ff;">var</span> right = []; };</pre>    </div>    <p><span>然后,开始遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。</span></p>    <br />    <pre class="brush:javascript; toolbar: true; auto-links: false;">var quickSort = function(arr) {   if (arr.length <= 1) { return arr; }   var pivotIndex = Math.floor(arr.length / 2) ;   var pivot = arr.splice(pivotIndex, 1)[0];   var left = [];   var right = [];   for (var i = 0; i < arr.length; i++){     if (arr[i] < pivot) {       left.push(arr[i]);     } else {       right.push(arr[i]);     }   } };</pre>    <p><span>最后,使用递归不断重复这个过程,就可以得到排序后的数组。</span></p>    <pre class="brush:javascript; toolbar: true; auto-links: false;">var quickSort = function(arr) {   if (arr.length <= 1) { return arr; }   var pivotIndex = Math.floor(arr.length / 2);   var pivot = arr.splice(pivotIndex, 1);   var left = [];   var right = [];   for (var i = 0; i < arr.length; i++){     if (arr[i] < pivot) {       left.push(arr[i]);     } else {       right.push(arr[i]);     }   }   return quickSort(left).concat(pivot, quickSort(right)); };  var dataArray = [85,24,63,45,17,31,96,50]; console.log(dataArray.join(",")); console.log(quickSort(dataArray).join(","));</pre>    <br /> 作者:    <a href="/misc/goto?guid=4958973281544496322" target="_blank">阮一峰</a>