简单算法(二)

冒泡排序

针对前一节讲的 “桶排序” 的问题,当我们处理很大的数据,如:0~200000000,这种范围的数据,需要申请一个 200000000 的变量:这种非常浪费空间!,如果要进行小数的排序,显然这种”桶排序” 是无法解决这些问题的,接下来介绍冒泡排序

基本思想:每次比较两个相邻的元素,如果他们的顺序不对(就是不符合这样排序的)就把他们交换过来。

“冒泡排序” 原理是:每一趟只能确定将一个数归位。如果有 n 个数进行排序,就需要进行 n-1 趟.

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
31
32
33
34
#include <stdio.h>
int main(void)
{
//定义输入的个数最多有多少个
int a[100],i,j,t,n;
printf("请输入你想排序的个数:");
scanf("%d",&n);
//循环 n 个数到数组中
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//n个数的排序,只进行 n-1 次
for(i=1;i<=n-1;i++)
{ //这个 for 循环进行比较的次数 比如: 三个数 第一趟: 比较 3-1次 第二趟:3-2
// j表示的是数的位置
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]);
}
getchar();
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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
struct student
{
char name[21];
char score;
}; //创建结构体储存姓名和分数
int main(void)
{
struct student a[100],t;
int i, j , n;
printf("请输入要排序的数目: \n");
scanf("%d",&n);
//循环读入姓名和分数
for(i=1;i<=n;i++)
{
scanf("%s %d",a[i].name,&a[i].score);
}
//循环遍历的趟数
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j].score<a[j+1].score)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
//输出排序后的名字
for(int i=1;i<=n;i++)
{
printf("%s \n",a[i].name);
}
return 0;
}

冒泡排序的核心部分是双重嵌套循环。时间复杂度 O(N2) 下一节 –快速排序