冒泡排序

• 全称 Bubble sort

• 特点

  • 稳定
  • 时间复杂度
    • 最优 O(n)，完全有序时，只需遍历一次而无需交换
    • 最坏和平均 O(n2)

• 原理

  • 外层: flag循环
  • 内层: 先让循环暂时失效，然后取相邻两个，让较大的那个交换到右边
    • 如果一次交换都没发生，代表完全有序，则循环保持失效状态，外层可结束
    • 如果至少发生一次交换，代表不完全有序，则循环改为有效状态，外层继续
    • 最终让最大的数冒泡到最右侧

let bubbleSort = (arr) => {
    const len = arr.length;
    let flag = true;
    while (flag) {
        flag = false;
        for (let i = 0; i < len - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                flag = true;
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            }
        }
    }
}

let shuffle = (arr) => {
    let n = arr.length;
    while (n > 0) {
        const random = (Math.random() * n--) >>> 0;
        [arr[random], arr[n]] = [arr[n], arr[random]];
    }
    return arr;
}

(() => {
    let testArr = [5, 7, 3, 4, 2, 6, 1];
    shuffle(testArr);
    bubbleSort(testArr);
    console.log(testArr);
})()

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;

void bubbleSort(vector<int>& nums) {
    int len = nums.size();
    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = 0; i < len - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                flag = true;
                swap(nums[i], nums[i + 1]);
            }
        }
    }
};

void shuffle(vector<int>& arr) {
    int n = arr.size();
    srand(time(NULL));
    while (n--) {
        const int random = rand() % arr.size();
        swap(arr[n], arr[random]);
    }
}

int main() {
    vector<int> testArr = {5, 7, 3, 4, 2, 6, 1};
    shuffle(testArr);
    bubbleSort(testArr);
    for(auto e: testArr) cout<<e<<endl;
    return 0;
}