冒泡排序

(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;

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信