冒泡排序

把⼩的元素往前调或者把⼤的元素往后调，⽐较是相邻的两个元素⽐较，交换也发⽣在这两个元素之间。

• 外循环表示需要N-1轮循环
• 内循环表示每轮循环需要比较的次数
• 如果前面的元素比后面的大，则交换

//bubbleSort.h
#ifndef _BUBBLE_SORT_H_
#define _BUBBLE_SORT_H_

#include <vector>
    
using std::vector; 
using std::swap;
        
void bubbleSort(vector<int>& nums);
#endif //_BUBBLE_SORT_H_

//bubbleSort.cc
#include "bubbleSort.h"

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

时间复杂度O(n²)

空间复杂度O(1)

//main.cc
#include <iostream>                                                           
#include <vector>
#include <cstdlib>
#include <ctime>
#include "bubbleSort.h"

using std::cout;
using std::endl;
using std::vector;
using std::srand;
using std::time;

const int dataSize = 10;
        
void getTestDate(vector<int> &nums) {
    srand(time(nullptr));
    for(int i = 0; i < dataSize; ++i){
        nums.push_back(rand()%99);
    }
}

void print(const vector<int> &nums) {
    for(auto i : nums) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    vector<int> nums;
    getTestDate(nums);
    print(nums);
    bubbleSort(nums);
    print(nums);
}