常见排序方案

• let arr = [4, 2, 1, 5, 6, 7, 8, 6, 5, 6, 7, 9, 9, 0, 0]

冒泡

时间：O(n^2) 稳定

function sort(arr) {
    let flag = null
    for (let i = 0; i < arr.length; i++) {
        flag = true
        for (let j = 0; j < arr.length - 1 - i; j++) {
            flag = false // 如果有一轮冒泡没进入，则说明已经排序完成了
            if (arr[j] > arr[j + 1])[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
        if(flag) break;
    }
    return arr
}
console.log(sort(arr))

快排

时间：O(nlogN) 或 O(n^2) 不稳定空间：logN

function quickSort(arr) {
    if(arr.length <= 1) return arr
    // 1.得到基准值
    let midIndex = Math.floor(arr.length / 2)
    let midItem = arr.splice(midIndex, 1)[0] 
    // 2.声明两个数组，比基准值小的放左边，比基准值大的放右边
    let left = []
    let right = []
    arr.forEach(item => {
        if(item < midItem) {
            left.push(item)
        } else {
            right.push(item)
        }
    })
    // 3.递归左边的数组quickSort(left)得到排好
    return quickSort(left).concat(midItem, quickSort(right))
}
console.log(arr)
console.log(quickSort(arr))