快速排序（Quicksort）的Javascript实现

     <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>