跳到主要内容

冒泡排序

2024年04月03日
柏拉文
越努力，越幸运

一、认识​

冒泡排序是排序算法中较为简单的一种，英文称为Bubble Sort。它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。

特点:

  • 稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面,所以冒泡属于稳定排序
  • 原地排序: 在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序
  • 排序方式: In-place (不占用额外内存，只占用常数内存)
  • 时间复杂度: O(n2n^{2}) [n 代表数据规模及数据量大小]
  • 空间复杂度: O(1)

扩展:

  • 排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

  • 冒泡排序和选择排序的相同点和不同点:
    • 相同点:
      • 都是两层循环，时间复杂度都为 O(n^2)
      • 都只使用有限个变量，空间复杂度 O(1)。
    • 不同点:
      • 冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值 / 最大值的下标，遍历完成后才交换，减少了交换次数。
      • 冒泡排序法是稳定的，选择排序法是不稳定的。

二、思想​

它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。

三、实现​

3.1 基础版​

function sortArray(nums) {
    for(let i=0;i<nums.length-1;i++){
        for(let j=0;j<nums.length-1-i;j++){
            if(nums[j]>nums[j+1]){
                [nums[j],nums[j+1]]=[nums[j+1],nums[j]];
            }
        }
    }
    return nums;
};

性能分析:

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

3.2 记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序​

function sortArray(nums) {
    let swapped=true;
    for(let i=0;i<nums.length-1;i++){
        if(!swapped){
            break;
        }
        swapped=false;
        for(let j=0;j<nums.length-1-i;j++){
            if(nums[j]>nums[j+1]){
                [nums[j],nums[j+1]]=[nums[j+1],nums[j]];
                swapped=true;
            }
        }
    }
    return nums;
};

性能分析:

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

3.3 记录上次发生交换的位置，下一轮排序时只比较到此位置​

function sortArray(nums) {
    let swapped=true;
    let indexOfLast=nums.length-1;
    let swappedIndex=-1;
    while(swapped){
        swapped=false;
        for(let i=0;i<indexOfLast;i++){
            if(nums[i]>nums[i+1]){
                [nums[i],nums[i+1]]=[nums[i+1],nums[i]];
                swapped=true;
                swappedIndex=i;
            }
        }
        indexOfLast=swappedIndex;
    }
    return nums;
};

性能分析:

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