邻居好说话——冒泡排序

冒泡排序

---

前言

先来看冒泡排序得基本思想：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。
冒泡排序的原理是：每一趟只能确定将一个数归位，即每一趟只能确定将末位上的数归位，第二趟将倒数第二个数归位依次类推。

一、什么是冒泡排序

让我们来看一个栗子：
有8个数组成一个无序数列：5，8，6，3，9，2，1，7，希望从小到大排序。
按照冒泡排序的思想，我们要把相邻的元素两两比较，根据大小来交换元素的位置，过程如下：
首先让5和8比较，发现5比8要小，因此元素位置不变。接下来让8和6比较，发现8比6要大，所以8和6交换位置。

继续让8和3比较，发现8比3要大，所以8和3交换位置。

依次类推，最后

然后进行第二轮比较

依次类推

原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2)

二、冒泡排序代码

#include
int main()
{
	int a[100],i,j,t,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
	//冒泡排序核心部分 
	for(i=1;i<=n-1;i++)//n个数排序只需要进行n-1次 
	{
	for(j=1;j<=n-i;j++)//从第一位开始比较，比到最后一个尚未归位的数
	if(a[j]<a[j+1])//比较大小并交换 
	{
		t=a[j];
		a[j]=a[j+1];
		a[j+1]=t;
		
	 } 
	}
	for(i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	 } 
	 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

理解一下这段程序你就明白了
下面解决上一节的问题怎么带上姓名
看这一段代码
t是结构体

#include
struct xuesheng
{
	char name[21];
	int score;
 }; //这里定义一个结构体用来存储姓名和分数
 int main()
 {
 	struct xuesheng a[100],t;
 	int i,j,n;
 	scanf("%d",&n);
 	for(i=1;i<=n;i++)
 	scanf("%s %d",&a[i].name,&a[i].score);
 	for(i=1;i<=n-1;i++)
 	{
	 for(j=1;j<=n-1;j++)
	 {
	 	if(a[j].score<a[j+1].score)//对分数进行比较 
	 	{
	 		t=a[j];
	 		a[j]=a[j+1];
	 		a[j+1]=t;
		 }
	  } 
	  
	 }
	 for(i=1;i<=n;i++)
	  printf("%s\n",a[i].name); 
  } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

t是int

#include
struct xuesheng
{
	char name[21];
	int score;
 }; //这里定义一个结构体用来存储姓名和分数
 int main()
 {
 	struct xuesheng a[100];
 	int i,j,n,t;
 	scanf("%d",&n);
 	for(i=1;i<=n;i++)
 	scanf("%s %d",&a[i].name,&a[i].score);
 	for(i=1;i<=n-1;i++)
 	{
	 for(j=1;j<=n-1;j++)
	 {
	 	if(a[j].score<a[j+1].score)//对分数进行比较 
	 	{
	 		t=a[j].score;
	 		a[j].score=a[j+1].score;
	 		a[j+1].score=t;
		 }
	  } 
	  
	 }
	 for(i=1;i<=n;i++)
	  printf("%s %d ",a[i].name,a[i].score); 
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

代码里引用了结构体，下面介绍一下结构体

struct Student{         //声明结构体
    char name[20];      //姓名
    int num;            //学号
    float score;        //成绩
};
struct Student stu1;    //定义结构体变量
1
2
3
4
5
6

struct Student{                 //声明结构体 Student
    char name[20];               
    int num;                    
    float score;                 
}stu = {"Mike", 15, 91};        //注意初始化值的类型和顺序要与结构体声明时成员的类型和顺序一致
1
2
3
4
5

总结

冒泡排序的核心部分就是双重嵌套循环