實(shí)現(xiàn)快速排序

這里我們將介紹一種中間排序算法：快速排序?？焖倥判蚴菍?duì)冒泡排序的一種改進(jìn)，它是由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

簡(jiǎn)單的說，快速排序就是在數(shù)組中找一個(gè)基準(zhǔn)值，比基準(zhǔn)值大的為一組，比基準(zhǔn)值小的為另外一組，再分別對(duì)每組進(jìn)行快速排序，直到所有值都依照一定順序進(jìn)行排列為止。下面讓我們通過一個(gè)簡(jiǎn)單的例子來了解快速排序：

數(shù)組[6,1,2,7,9,3,4,5,10,8]

第一趟:

我們選擇6(隨機(jī)選取)為基準(zhǔn)值,則根據(jù)基準(zhǔn)值,數(shù)組經(jīng)過第一次排序后,可以分成

[3,1,2,5,4],6,[9,7,10,8]

第二趟:

我們對(duì)[3,1,2,5,4]進(jìn)行快速排序,依然隨機(jī)選擇一個(gè)基準(zhǔn)值,假設(shè)3為基準(zhǔn)值,則第二趟排序后結(jié)果為

[1,2],3,[5,4]

...

這樣,經(jīng)過不斷的分組,排序,我們最終就得到了一個(gè)有序數(shù)組

快速排序是一種非常有效的排序方法，平均提供O(nlog(n))性能。它也比較容易實(shí)現(xiàn)。快速排序?qū)儆谝环N流行,有用,高效的排序方法。

var array = [];
(function createArray(size) {
  array.push(+(Math.random() * 100).toFixed(0));
  return (size > 1) ? createArray(size - 1) : undefined;
})(12);


function quickSort(array) {
  // change code below this line
  if (array.length<=1) {
      return array
      }
      var arrayIndex=Math.floor(array.length/2)//選取基準(zhǔn)點(diǎn)
      var arr=array.splice(arrayIndex,1)//基準(zhǔn)值
      var left=[],right=[];
      //遍歷數(shù)組進(jìn)行分配
      for (var i = 0; i < array.length; i++) {
         if(array[i]>arr){
             right.push(array[i]);
         }else{
             left.push(array[i]);
         }
      }
       var result=quickSort(left).concat(arr,quickSort(right))//遞歸操作
  // change code above this line
  return result;
}
quickSort(array)