【算法】排序——冒泡排序

冒泡排序

（1）冒泡排序的基本思想是在排序过程中，对待排序序列中相邻两个元素关键字的值进行比较，当不满足排序要求时就交换两个元素的位置。这样，关键字值较小的元素就会像水中的气泡一样逐层浮起，直至完成排序过程。利用蛮力法容易实现冒泡排序的算法涉及。

（2）在某一遍扫描中，对元素list[i]与list[i+1]的关键字进行比较，若list[i]>list[i+1]，则交换list[i]与list[i+1]的位置，这样重复扫描，直到在某一遍扫描时不存在list[i]>list[i+1]的情况，排序结束。

（3）在经过一次扫描后，关键字最大的元素就沉底了，排到了线性表的最后一个位置，且在比较过程中，凡是关键字较小的元素都浮上了一层。在第i+1次扫描时，不必自上而下的比较线性表中所有的相邻元素对，只需要比较从list[1]到list[N-1]的相邻元素就可以了，这是因为经过i次扫描后，线性表中元素list[N-i+1]到list[N]的元素都已经在正确的位置了，不必再次扫描。实际排序过程中，如果经过k趟冒泡排序后，就已经排好序了，就不必继续进行后序的排序，为此可以设置一个标志flag，用来记录每趟扫描是否还存在元素的交换，若已经没有元素的交换，则排序可以提前结束。

（4）冒泡排序算法

void bubbleSort(int list[],int n){
    int i=1,j,t,flag=1;
    for(i=1;i<n&&flag;i++){
        flag=0;
        for(j=1;j<=n-1;j++){
            if(list[j]>list[j+1]){
                t=list[j];
                list[j]=list[j+1];
                list[j+1]=t;
                flag=1;
            }
        }
    }
} 

（5）完整程序 

#include<stdio.h>
#define N 20
int list[N+1];
void insertSort(int list[],int n){
    int i,j;
    for(i=2;i<=n;i++){
        list[0]=list[i];
        j=i-1;
        while(j>0&&list[0]<list[j]){
            list[j+1]=list[j];
            j--;
        }
        list[j+1]=list[0];
    }
}
void bubbleSort(int list[],int n){
    int i=1,j,t,flag=1;
    for(i=1;i<n&&flag;i++){
        flag=0;
        for(j=1;j<=n-1;j++){
            if(list[j]>list[j+1]){
                t=list[j];
                list[j]=list[j+1];
                list[j+1]=t;
                flag=1;
            }
        }
    }
}
int main(){
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&list[i]);
    }
    //insertSort(list,n);
    bubbleSort(list,n);
    for(i=1;i<=n;i++){
        printf("%d ",list[i]);
    } 
    return 0;
}