快速排序

什么是快速排序？

快速排序(Quicksort)使用分治法策略
选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

如何实现快速排序

• 从数列中挑出一个基准值
• 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置
• 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序

// 快速排序
function quickSort(arr) {
    if (arr.length < 1) {
        return arr;
    }
    const leftArr = [];
    const rightArr = [];
    // 删除是为了保证传进的数据不存在跟自己对比，
      // 如果不删除会导致永远存在一条数据进入死循环
    const currentNum = arr.splice(0, 1);
    arr.forEach(item => {
        if (item < currentNum) {
            leftArr.push(item);
        } else {
            rightArr.push(item);
        }
    })
    return [
      ...quickSort(leftArr),
      ...currentNum,
      ...quickSort(rightArr)
    ];
}
// 随机生成一个数组、测试排序的性能
function RandomNumArr() {
    const arr = [];
    for(let i = 0; i < 1000000; i++) {
        arr.push(parseInt(Math.random()*1000));
    }
    console.log(new Date());
    return arr;
}
// console.log(quickSort([2,9,20,0,30,22,3,1,94,2]))
console.log(quickSort(RandomNumArr()));
// console.log(new Date());