冒泡排序算法

冒泡排序

思想：每一趟排序，从左往右扫描数组，

如果a[i]>a[i+1],就把她们交换 执行n次，数列就有序了。

正确性证明：第一次排序时，最大值将转到最右边， 第二次排序时，次大值将转到最右边......

以此类推，n次之后n个数都到了指定位置

代码实现：

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

 时间复杂度分析：O（n^2）