javascript高级排序算法之快速排序（快排）

javascript高级排序算法之快速排序（快排）
我们之前讨论了javascript基本排序算法

• 冒泡排序
• 选择排序
• 插入排序

简单复习：

冒泡排序：

1. 比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2. 第一轮的时候最后一个元素应该是最大的一个。
3. 按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

选择排序：
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕。

插入排序：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

今天开始讨论高级排序算法

快速排序

快速排序是处理大量数据最快的排序算法之一，一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列，然后不断重复这个步骤直到所有数据都是有序的。
首先需要在数据列表中选择一个元素作为基准值（pivot，这个变量我们后面会用到），数据排序围绕着基准值进行，（基准值可以是任意一个位置的数，不过一般选择中间的数字或者最左边的数字），每一轮结束后，比该基数小的数都位于该基数的左边，比该基数大的数都位于该基数的右边。然后再分别对基数左边和右边的数组进行相同的操作，直到数组中只有一个元素时，返回该数组。
简单说：（从小到大排序）

1. 选择一个基准元素，将数据列表分成两个子序列；
2. 对数据列表进行重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值的元素放在基准值的后面；
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2。

看一个🌰：

let arr = []

function arrData(num) {
    for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * num + 1)
    }
}
arrData(10)
function qSort(myArr) {
    if(myArr.length===0){
        return[]
    }
    let smallArr=[]
    let bigArr = []
    let pivot = myArr[0]
    for(let i =1;i<myArr.length;i++){
        if(myArr[i]<pivot){
            smallArr.push(myArr[i])
        }else{
            bigArr.push(myArr[i])
        }
    }
    // return qSort(smallArr).concat(pivot,qSort(bigArr))
    return [...qSort(smallArr),pivot,...qSort(bigArr)]
}
console.log(qSort(arr)); //=>[4, 5, 7, 8, 8, 8, 8, 8, 9, 10]

先解释一下最后的那句return

return qSort(smallArr).concat(pivot,qSort(bigArr))
return [...qSort(smallArr),pivot,...qSort(bigArr)]

两句是等效的，第二句不过是是用来es6，相信你是懂的。
在qSort方法中的return里调用了qSort方法，哦，很明显，这是一个递归了，好了，递归就必须有个停止的条件，
所以前面的if判断就很有必要了，否则就会报错（递归常见错误）

👆的🌰，基准值取的是第一个元素，我们也可以取中间的那一个，
⚠️做比较的时候，要把基准排除

function qSort(myArr) {
  if (myArr.length === 0) {
        return [];
      }
    let pivotIndex = Math.floor(myArr.length / 2);
    //找基准，并把基准从原数组删除
    let pivot = myArr.splice(pivotIndex, 1)[0];
    //定义左右数组
    let left = [];
    let right = [];
    //比基准小的放在left，比基准大的放在right
    for (let i = 0; i < myArr.length; i++) {
        if (myArr[i] <= pivot) {
            left.push(myArr[i]);
        } else {
            right.push(myArr[i]);
        }
    }
    //递归
    return [...qSort(left),pivot,...qSort(right)]
}
console.log(qSort(arr));//=>?[1, 2, 3, 5, 5, 6, 9, 9, 9, 10]

性能比较

我们上次对三个基本排序做了性能比较，我们在看看高级排序的性能如何呢？
我门依然使用 console.time和console.timeEnd
代码如下

let arr = []

    function arrData(num) {
        for (let i = 0; i < num; i++) {
            arr[i] = Math.floor(Math.random() * num + 1)
        }
    }
arrData(10)

function jssort(myArr) {
    console.time(`${myArr.length}长度冒泡排序耗时`)
    for (let i = 0; i < myArr.length - 1; i++) { //要循环多少次
        for (let j = 0; j < myArr.length - 1; j++) { //要移动几次
            if (myArr[j] > myArr[j + 1]) {
                [myArr[j], myArr[j + 1]] = [myArr[j + 1], myArr[j]]
            }
        }
    }
        console.timeEnd(`${myArr.length}长度冒泡排序耗时`)
        return myArr;
    }

function selectSort(myArr) {
    console.time(`${myArr.length}长度选择排序耗时`)
    let minIndex, temp;
    var len = myArr.length;
    for (let i = 0; i < myArr.length - 1; i++) {
          minIndex = i;
          for (let j = i + 1; j < myArr.length; j++) {
              if (myArr[j] < myArr[minIndex]) {
                  minIndex = j;
              }
          }
          [myArr[i], myArr[minIndex]] = [myArr[minIndex], myArr[i]]
      }
        console.timeEnd(`${myArr.length}长度选择排序耗时`)
        return myArr;
    }

function insertSort(myArr) {
    console.time(`${myArr.length}长度插入排序耗时`)
    let temp, j;
    for (let i = 1; i < myArr.length; i++) {
        temp = myArr[i];
        j = i;
        while (j > 0 && myArr[j - 1] > temp) {
            myArr[j] = myArr[j - 1];
            j--;
        }
        myArr[j] = temp;
    }
    console.timeEnd(`${myArr.length}长度插入排序耗时`)
    return myArr
}

function qSort(myArr) {
    if (myArr.length === 0) {
        return []
    }
    let smallArr = []
    let bigArr = []
    let pivot = myArr[0]
    for (let i = 1; i < myArr.length; i++) {
        if (myArr[i] < pivot) {
            smallArr.push(myArr[i])
        } else {
            bigArr.push(myArr[i])
        }
    }
    return [...qSort(smallArr), pivot, ...qSort(bigArr)]
}
// jssort(arr)
// selectSort(arr)
// insertSort(arr)
// console.time(`${arr.length}长度快速排序耗时`)
// qSort(arr)
// console.timeEnd(`${arr.length}长度快速排序耗时`)

为了防止相互之间的干扰，我们每次运行，只执行一个排序方法
长度10：
冒泡： 0.0400390625ms
选择： 0.041015625ms
插入：0.01611328125ms
快速：0.10302734375ms

长度为10的时候，快速并不快
继续看
长度100：
冒泡： 2.80712890625ms
选择： 0.306884765625ms
插入： 0.201171875ms
快速： 0.22998046875ms
长度为100的时候，差距渐渐产生
长度1000：
冒泡： 11.09912109375ms
选择： 5.80615234375ms
插入： 2.330810546875ms
快速： 4.80908203125ms
长度10000：
冒泡： 583.984130859375ms
选择： 62.747802734375ms
插入： 28.248046875ms
快速： 43.587158203125ms

到这个数量级，冒泡可以考虑放弃了
长度100000：
冒泡： 51715.775146484375ms
选择： 4505.01513671875ms
插入：2527.210205078125ms
快速： 120.48193359375ms
看到时间上的差距了

我们得出这样的一个结论：

快速排序非常适用于大型数据集合，在处理小数据集合时，反而会慢