算法：快速排序

排序分为交换排序、选择排序、插入排序、归并排序、基数排序
快速排序和冒泡排序数据交换排序

首先，定义一个quickSort函数，它的参数是一个数组。

function quickSort(arr){
    
}

然后，检查数组的元素个数，如果小于等于1，就返回。

function quickSort(arr){
    if(arr.length<=1){
        return arr;
    }
}

接着，选择”基准”（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。

function quickSort(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 = [];
}

然后，开始遍历数组，小于”基准”的元素放入左边的子集，大于等于基准的元素放入右边的子集。

function quickSort(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 in arr){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
}

最后，使用递归不断重复这个过程，就可以得到排序后的数组。

function quickSort(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 in arr){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot],quickSort(right));
}

优化：选一个好的基准：随机选取三个数，排序取中

时间复杂度：nlogn