快速排序

"快速排序"的思想很简单，整个排序过程只需要三步：

• （1）在数据集之中，选择一个元素作为"基准"（pivot）。

• （2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。

• （3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

代码：
容易理解，但是内存占用较多：

var quickSort = function(arr) {
　　if ( arr && arr.length <= 1 ) { 
         return arr; 
    }
　　var middleIndex = Math.floor(arr.length / 2);
　　var middleValue = arr.splice(middleIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for ( let = 0; i < arr.length; i++ ){
　　　　if ( arr[i] < middleValue ) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([middleValue], quickSort(right));
};

比较复杂，但是内存占用比较少：
原理：将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成.

function quickSort(array, left, right){
     var left = typeof left === 'number' ? left : 0,
         right = typeof right === 'number' ? right : array.length - 1,
         partitionIndex;

     if ( left < right ){
         partitionIndex = partition(array, left, right);  //切分的基准值
         
         quickSort(array, left, partitionIndex-1);
         quickSort(array, partitionIndex + 1, right)
     }

     return array;
}

function partition(array, left, right){   //分区操作
     for ( var i = left + 1, j = left; i <= right; i++ ){  //j是较小值存储位置的游标
           if ( array[i] < array[left] ){
                swap(i, ++j, array);      //以第一个元素为基准
           }
     }

     swap(left, j, array);   //将第一个元素移至中间
     return j;
}

function swap(left, right, array){
     var temp = array[left];

     array[left] = array[right];
     array[right] = temp;
}