简单算法(二)

发表于 | 分类于 | 阅读次数 |

冒泡排序

针对前一节讲的 “桶排序” 的问题，当我们处理很大的数据，如：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) 下一节 –快速排序

(*^▽^*)