Skip to main content

快速排序

算法模式：二分法​

时间复杂度为:O(nlogn) 思路：

  1. 防御性：长度小于 1 直接返回
  2. 获取中间值 middle
  3. 声明 left/right 空数组
  4. for 从 0 递增
    • 小于中间值：left.push(arr[i])
    • 大于中间值: right.push(arr[i])
  5. 返回 左递归+concat+右递归
var quickSort = (arr) => {
    // 为了排除小于空数组
    if(arr.length <= 1){return arr}

    // 获取中间值
    var middleIndex = Math.floor(arr.length/2)
    var middle = arr.splice(middleIndex,1)[0]

    var left = []
    var right = []

    for(let i = 0;i<arr.length;i++){
        if(arr[i] < middle){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }

    // 递归
    return quickSort(left).concat([middle],quickSort(right))
}

与归并排序区别：快速排序是对比中间值，归并排序是对比左右