首页 > 代码库 > 啊哈!算法第一章第二节---冒泡排序

啊哈!算法第一章第二节---冒泡排序

冒泡排序冒泡排序的基本思想是:每次比较相邻两个元素的大小,如果顺序错误就交换位置。

比如说有5个数12 35 99 18 76,要从大到小排序。所以越小的越靠后

首先比较第1位和第2位的大小。由于12小于35,所以他们两个交换位置。交换后:35 12 99 18 76.

然后比较第2位和第3位的大小。由于12小于99,所以他们两个交换位置。交换后:35 99 12 18 76.

然后重复上述步骤,比较第3位和第4位,第4位和第5位。四次比较后5个数的顺序是:35 99 18 76 12.这样我们就把最小的一个数归位了。每将一个数归位我们将其称为‘一趟’。下面就是重复上面的过程,将第二小的数归位,第三小的数归位,这样来到了第四趟。虽然对于这五个数已经排好位置,但是这只是巧合,换一下数据就不一定了。

 

通过上面的例子,发现冒泡排序的原理是:每趟将一个数归位。即第一趟只能将第五位上的数归位,第二趟只能将倒数第二位上的数归位,第三趟将第三位上的数归位,而在前面还有两个位置上的书没有归位,还需要进行第四趟。

第四趟只需比较第一位和第二位的数,这样不仅第二位确定了,第一位也确定了。

综上所述:如果有n个数需要排序,只需将n-1个数归位,也就是要进行n-1趟操作。每一趟都需要从第一位开始进行相邻两个数的比较,根据要求(从大到小还是从小到大)来判断位置是否正确,不正确就换位。直到最后一个尚未归位的数。注意,已经归位的数无需再次进行比较

看一下代码:

 

#include <stdio.h>
int main(){
    int n,a[100],i,j,temp; 
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n-1;i++)  //只需进行n-1趟比较
        for(j=0;j<n-i-1;j++) //每次都从第一位开始比较,已归位不用再比较
            if(a[j]<a[j+1]){
                temp=a[j];  //从大到小排序,小的数排在后面
                a[j]=a[j+1];
                a[j+1]=temp;
            }
    for(i=0;i<n;i++)
        printf("%d",a[i]); //输出结果
    return 0;
}

 

 

 

用这种方法可以弥补上一节的问题,加一个结构体。

 1 #include <stdio.h>
 2 struct student{
 3     char name[21];
 4     int score;
 5 }; //存放学生姓名和分数
 6 int main(){
 7     struct student a[100],temp;
 8     int i,j,n;
 9     scanf("%d",&n);
10     for(i=0;i<n;i++)
11         scanf("%s %d",a[i].name,&a[i].score);
12     for(i=0;i<n-1;i++)
13         for(j=0;j<n-i-1;j++)
14             if(a[j].score<a[j+1].score){ //从高到低排序,比较分数
15                 temp=a[j];
16                 a[j]=a[j+1];
17                 a[j+1]=temp;
18             }
19     for(i=0;i<n;i++) //输出人名
20         printf("%s\n",a[i].name);
21     return 0;
22 }

冒泡排序的核心是双重嵌套循环.

 

啊哈!算法第一章第二节---冒泡排序