冒泡排序

冒泡排序是一种交换排序

#include<iostream>
using namespace std;

void bubble_sort(int a[],int n){
    for (int i = 0; i < n;i++){//外循环，趟数
        //内循环
        //第0趟：a[0]--a[n-1]都是无序区，如果不满足a[j]<a[j-1]，则相邻的交换
        //第1趟，a[0]有序，a[1]--a[n-1]是无序区，....
        //....
        //第i趟，a[0]--a[i-1]是有序区，a[i]--a[n-1]是无序区，...

        for (int j = n - 1; j>i;j--){
            if (a[j]<a[j-1]){
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}

int main(){
    int a[] = { 49, 38, 65, 97, 76, 13, 27 };

    bubble_sort(a,7);

    for (int i = 0; i < 7;i++){
        cout << a[i]<<" ";
    }

    return 0;
}

代码还有优化的空间，如果发现内循环中没有发生一次交换，则说明无序区其实已经有序了，则程序可以终止。

#include<iostream>
using namespace std;

void bubble_sort(int a[],int n){
    for (int i = 0; i < n;i++){
        int ok = 0;
        for (int j = n - 1; j>i;j--){
            if (a[j]<a[j-1]){
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                ok = 1;
            }

        }

        if (!ok){
            return;
        }
    }
}


int main(){
    int a[] = { 49, 38, 65, 97, 76, 13, 27 };

    bubble_sort(a,7);

    for (int i = 0; i < 7;i++){
        cout << a[i]<<" ";
    }

    return 0;
}