冒泡排序

冒泡排序算法思想

提示

冒泡排序是一种简单的排序算法，它通过反复交换相邻的未正确排序的元素，使较大的元素像泡泡一样浮到数组的顶端。其核心思想包括：

1. 比较与交换：比较相邻两个元素，如果它们的顺序错误就把它们交换过来。
2. 冒泡：每一轮排序后，可以确保该轮最大的元素被交换到正确的位置。
3. 优化：如果在一次遍历中没有进行交换，那么数组已经有序，可以提前结束排序。

冒泡排序算法步骤

假设数组的长度为 $n$。

1. 外层循环控制所有的排序回合，最坏情况下需要 $n-1$ 次排序。
2. 内层循环负责进行相邻元素的比较和可能的交换，第 $i$ 轮排序需要比较 $n-i$ 次。
3. 使用一个标记变量 swapped 来检查本轮排序中是否发生了交换，若无交换，则数组已经有序，排序提前结束。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var bubbleSort = function(nums) {
    let n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换相邻元素
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                swapped = true;
            }
        }
        // 如果一轮中没有发生任何交换，则数组已排序完成
        if (!swapped) {
            break;
        }
    }
    return nums;
};

复杂度

• 时间复杂度：
  • 最佳时间复杂度：$O(n)$。最好的情况下（初始时序列已经是升序排列），只需经过 $1$ 趟排序，总共经过 $n$ 次元素之间的比较，并且不移动元素，算法就可以结束排序。因此，冒泡排序算法的最佳时间复杂度为 $O(n)$。
  • 最坏时间复杂度：$(n^2)$。最差的情况下（初始时序列已经是降序排列，或者最小值元素处在序列的最后），则需要进行 $n$ 次排序，总共 $\sum^{n}_{i = 2} i - 1 = \frac{n(n-1)}{2}$ 次比。
• 空间复杂度：$O(1)$​。

排序稳定性

由于元素交换是在相邻元素之间进行的，不会改变相等元素的相对顺序，因此，冒泡排序法是一种稳定排序算法。