冒泡排序

思路

需要遍历 length - 1 次
每一次遍历
都从后往前进行比较，
相邻的两两比较大小，小的向前浮动
时间复杂度 O(n²)

function bubbleSort(target) {
    let temp = null

    for(let i = 0; i < target.length - 1; i++) {
        for(let j = target.length - 1; j > i; j--) {
            if (target[j] < target[j - 1]) {
                temp = target[j]
                target[j] = target[j - 1]
                target[j - 1] = temp
            }
        }

        console.log(`第 ${i + 1} 次排序`)
    }

    return target
}

console.log(bubbleSort([23, 32, 5, 72, 12, 1]))

运行结果

缺点：

当目标对象是已经排序好的数据
也需要进行多次遍历

console.log(bubbleSort([1, 2, 3, 4, 5, 6]))

运行结果

优化

定义一个布尔值
在遍历每一次的时候，如果发生位置交换，就改变布尔值
当这一次循环结束之后，判断该布尔值是否变化
变化了则继续下一次，没变则退出

function bubbleSort(target) {
    let temp = null
    let flag = false

    for(let i = 0; i < target.length - 1; i++) {
        for(let j = target.length - 1; j > i; j--) {
            if (target[j] < target[j - 1]) {
                temp = target[j]
                target[j] = target[j - 1]
                target[j - 1] = temp
                flag = true
            }
        }

        console.log(`第 ${i + 1} 次排序`)
        if (!flag) break
    }

    return target
}

console.log(bubbleSort([1, 2, 3, 4, 5, 6]))

运行结果

选择排序

遍历 length - 1 次
从左到右开始找，每遍历一次将最小值跟当前遍历的第一个元素交换
时间复杂度 O(n²)

function selctionSort(target) {
    for (let i = 0; i < target.length - 1; i++) {
        let min = target[i]
        let minIndex = i

        for (let j = i + 1; j < target.length; j++) {
            if (target[j] < min) {
                min = target[j]
                minIndex = j
            }
        }

        console.log(`第${i + 1}次循环`, target)
        // 减少循环次数
        if (minIndex === i) break
        target[minIndex] = target[i]
        target[i] = min
    }

    return target
}

console.log(selctionSort([23, 32, 5, 72, 12, 1]))
console.log(selctionSort([1, 2, 3, 4, 5, 6])) 

运行结果

插入排序

遍历 length - 1 次
从 i + 1 项开始往前遍历，两两比较小的往前移动，
时间复杂度 O(n2)

function insertionSort(target) {
    let temp

    for (let i = 0; i < target.length - 1; i++) {

        for (let j = i + 1; j > 0; j--) {
            if (target[j] < target[j - 1]) {
                temp = target[j - 1]
                target[j - 1] = target[j]
                target[j] = temp
            } else {
                // 当不小于已排序好的最大值时
                // 退出每次遍历，进行下一次
                break
            }
        }

        console.log(`第${i + 1}次循环`, target)
    }

    return target
}
console.log(insertionSort([23, 32, 5, 72, 12, 1]))

运行结果

快速排序

/**
 参数说明
 target 需要排序的目标数组
 l  需要排序的起始项
 r  需要排序的终止项
 */
function quickSort(target, l, r) {
    if (l >= r) return

    let i = l; let j = r; let key = target[l];//选择第一个数为key

    while (i < j) {

        while (i < j && target[j] >= key)//从右向左找第一个小于key的值
            j--;
        if (i < j) {
            target[i] = target[j];
            i++;
        }

        while (i < j && target[i] < key)//从左向右找第一个大于key的值
            i++;

        if (i < j) {
            target[j] = target[i];
            j--;
        }
    }
    //i == j
    target[i] = key;
    quickSort(target, l, i - 1);//递归调用
    quickSort(target, i + 1, r);//递归调用
    return target
}

console.log(quickSort([23, 32, 5, 72, 12, 1, 2], 0, 5))
console.log(quickSort([23, 32, 5, 72, 12, 1], 4, 5))

运行结果

【笔记不易，如对您有帮助，请点赞，谢谢】