【数据结构学习笔记】冒泡排序

【数据结构学习笔记】冒泡排序

参考电子书：排序算法精讲

算法原理

对未排序的元素进行多次遍历，每次遍历都将相邻的两个元素进行比较，如果它们的顺序错误就交换它们的位置。在每一轮遍历后，最大的元素会被冒泡到序列的末端。这个过程会一直重复，直到没有需要交换的元素为止，此时序列已经排好序

const nums = [2, 5, 7, 4, 1];

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

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

优化方式

• 当 i 为 nums.length - 1 时，nums.length - 1 - i 为 0，可以直接跳过此轮

const nums = [2, 5, 7, 4, 1];

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

• 如果某一轮没有发送交换，那么后续也不会发生交换，数组已经有序

const nums = [2, 5, 7, 4, 1];

for (let i = 0; i < nums.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < nums.length - i - 1; j++) {
        if (data[j] > data[j + 1]) {
            const temp = data[j];
            data[j] = data[j + 1];
            data[j + 1] = temp;
            swapped = true;
        }
    }
    if (!swapped) break;
}

• 记录当前轮次最后一次发生交换的位置，后面的序列是有序的，可以跳过

const nums = [2, 5, 7, 4, 1];

let swapped;
let swappedIndex = - 1;
let indexOfLastUnsortedElement = arr.length - 1;
for (let i = 0; i < nums.length - 1; i++) {
    swapped = false;
    for (let j = 0; j < indexOfLastUnsortedElement; j++) {
        if (data[j] > data[j + 1]) {
            const temp = data[j];
            data[j] = data[j + 1];
            data[j + 1] = temp;
            swapped = true;
            swappedIndex = j;
        }
    }
    if (!swapped) break;
    indexOfLastUnsortedElement = swappedIndex;
}

相关例题

LC 283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。

/**
 * @param {number[][]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let swapped;
    for (let i = 0; i < nums.length - 1; i++) {
        swapped = false;
        for (let j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] === 0) {
                const temp = nums[j + 1];
                nums[j + 1] = nums[j];
                nums[j] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}