快速排序算法（JavaScript实现）

快速排序采用分治法的一个非常典型的应用

算法思想

快速排序使用分治法策略来把一个序列分为两个子序列，其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

时间复杂度

O(nlgn)

步骤：

• 从数列中挑出一个元素，称为"基准"（pivot）
• 所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
• 递归的把小于基准值元素的子数列和大于基准值元素的子数列排序

举例

现有一个数组：arr = [6,4,5,2,7]
那么先拿出一个基准：5
从左开始遍历该数组：

6  4  5  2  7
|
大于5

如果大于基准5则放在基准右边

4  5  6  2  7
      |
   放此位置

继续遍历：

4  5  6  2  7
|
小于5

如果小于基准5则放在基准左边，故位置不变，继续遍历：

4  5  6  2  7
         |
        小于5

则放在基准左边：

4  2  5  6  7
   |
放此位置

那么我们的一次遍历就完成了，以此类推，再遍历左边序列以及右边序列

代码实现

常用实现方法如下，c和java都可以：

function quick_sort(arr,low,high){
  var i = low;
  var j = high;
  var temp = arr[i];
  if(low < high){
    while(i < j){
      while(i<j && arr[j] >= temp){
        j--;
      }
      arr[i] = arr[j];
      while(i<j && arr[i] <= temp){
        i++;
      }
      arr[j] = arr[i];
    }
    arr[i] = temp;
    quick_sort(arr,low,i-1);
    quick_sort(arr,i+1,high);
  }
  else{
    return;
  }
}

var arr = [6,4,5,2,7];
quick_sort(arr,0,arr.length-1)
console.log(arr);   // [2,4,5,6,7]

以下方法只适用于JavaScript，因为使用了JavaScript的数组的方法，并且该方法空间复杂度比较大，因为多使用了两个数组

function quick_sort(arr) {　　
    if (arr.length <= 1) {
        return arr;
    }　　
    var middle = Math.floor(arr.length / 2);　　
    var pivot = arr.splice(middle, 1)[0];　　
    var low = [];　　
    var high = [];　　
    for (var i = 0; i < arr.length; i++) {　　　　
        if (arr[i] < pivot) {　　　　　　
            low.push(arr[i]);　　　　
        } else {　　　　　　
            high.push(arr[i]);　　　　
        }　　
    }　　
    return quickSort(low).concat([middleValue], quickSort(high));
}

var arr = [6,4,5,2,7];
quick_sort(arr);  // [2,4,5,6,7]

优化思路

• 对于小数组，可以采用插入排序，避免递归调用
• 采用子数组的一部分元素的中位数来切分数组