排序算法简单分析系列 - - 冒泡排序

2021/03/27 Algorithm 共 886 字,约 3 分钟

基本思想

首先这个排序的名字就比较形象,因此会比较容易理解。冒泡,气泡从水底往上漂浮,而重的石块会从水面向下沉。

一次排序:第一个元素开始,将其与第二个元素进行比较,若为逆序,则将这两个元素交换。随后,第二个元素再与第三个元素进行比较,依此类推,直到 n - 1 个元素与第 n 个元素进行比较交换为止。

代码分析

以下示例的排序是从小到大排序。

冒泡排序有个可以优化的点:在某一次排序过程中,发现没有置换元素,说明排序是已经排好了。那么就可以终止后续的代码执行。

这里可以通过一个变量来控制,在第一层循环中,初始化一个变量 isSorted = true,在第二层循环中,如若发生元素置换,则将其修改为 false,在后续就可以通过判断其状态,来决定是否提前终止循环。

const bubbleSort = (better = false, data = [1, 5, 7, 5, 2, 4, 6, 3, 9, 8, 44]) => {
    if (!Array.isArray(data)) throw Error('input not array');
    let count = 0;
    console.log(data);
    console.log('..');
    for (let i = 0; i < data.length - 1; i++) {
        let isSorted = true;
        for (let j = 0; j < data.length - i - 1; j++) {
            count++;
            // debugger;
            if (data[j] > data[j + 1]) {
                [data[j], data[j + 1]] = [data[j + 1], data[j]];
                isSorted = false;
            }
        }
        if (isSorted && better) {
            break;
        }
        console.log(`第${i + 1}次:`, data, { isSorted });
    }

    console.log(count);
    return data;
};

bubbleSort();

时间复杂度

两次 for 循环,时间复杂度:O(n^2)

稳定性

是稳定的排序方法

相关文章:

文档信息

Search

    Table of Contents