快速排序

题目

用 Javascript 实现快速排序，并说明时间复杂度。

思路

快速排序是基础算法之一，算法思路是固定的

• 找到中间位置 midValue
• 遍历数组，小于 midValue 放在 left ，大于 midValue 放在 right
• 继续递归，concat 拼接

splice 和 slice

代码实现时，获取 midValue 可以通过 splice 和 slice 两种方式

理论分析，slice 要优于 splice ，因为 splice 会修改原数组。
但实际性能测试发现两者接近。

但是，即便如此还是倾向于选择 slice —— 因为它不会改动原数组，类似于函数式编程

性能分析

快速排序 时间复杂度 O(n*logn) —— 有遍历，有二分

普通的排序算法（如冒泡排序）时间复杂度时 O(n^2)

答案

使用 slice 方案，参考 quick-sort.ts

/**
 * 快速排序（使用 splice）
 * @param arr number arr
 */
export function quickSort1(arr: number[]): number[] {
    const length = arr.length
    if (length === 0) return arr

    const midIndex = Math.floor(length / 2)
    const midValue = arr.splice(midIndex, 1)[0]

    const left: number[] = []
    const right: number[] = []

    // 注意：这里不用直接用 length ，而是用 arr.length 。因为 arr 已经被 splice 给修改了
    for (let i = 0; i < arr.length; i++) {
        const n = arr[i]
        if (n < midValue) {
            // 小于 midValue ，则放在 left
            left.push(n)
        } else {
            // 大于 midValue ，则放在 right
            right.push(n)
        }
    }

    return quickSort1(left).concat(
        [midValue],
        quickSort1(right)
    )
}

/**
 * 快速排序（使用 slice）
 * @param arr number arr
 */
export function quickSort2(arr: number[]): number[] {
    const length = arr.length
    if (length === 0) return arr

    const midIndex = Math.floor(length / 2)
    const midValue = arr.slice(midIndex, midIndex + 1)[0]

    const left: number[] = []
    const right: number[] = []

    for (let i = 0; i < length; i++) {
        if (i !== midIndex) {
            const n = arr[i]
            if (n < midValue) {
                // 小于 midValue ，则放在 left
                left.push(n)
            } else {
                // 大于 midValue ，则放在 right
                right.push(n)
            }
        }
    }

    return quickSort2(left).concat(
        [midValue],
        quickSort2(right)
    )
}

// // 功能测试
// const arr1 = [1, 6, 2, 7, 3, 8, 4, 9, 5]
// console.info(quickSort2(arr1))

// // 性能测试
// const arr1 = []
// for (let i = 0; i < 10 * 10000; i++) {
//     arr1.push(Math.floor(Math.random() * 1000))
// }
// console.time('quickSort1')
// quickSort1(arr1)
// console.timeEnd('quickSort1') // 74ms

// const arr2 = []
// for (let i = 0; i < 10 * 10000; i++) {
//     arr2.push(Math.floor(Math.random() * 1000))
// }
// console.time('quickSort2')
// quickSort2(arr2)
// console.timeEnd('quickSort2') // 82ms

// // 单独比较 splice 和 slice
// const arr1 = []
// for (let i = 0; i < 10 * 10000; i++) {
//     arr1.push(Math.floor(Math.random() * 1000))
// }
// console.time('splice')
// arr1.splice(5 * 10000, 1)
// console.timeEnd('splice')
// const arr2 = []
// for (let i = 0; i < 10 * 10000; i++) {
//     arr2.push(Math.floor(Math.random() * 1000))
// }
// console.time('slice')
// arr2.slice(5 * 10000, 5 * 10000 + 1)
// console.timeEnd('slice')

划重点

• 排序算法（基本功）
• 二分法的时间复杂度
• 注意数组的操作（ splice vs slice ）