简单算法(一)

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

从极客学院 wiki 中下载的电子书《坐在马桶上学算法》,虽然入门编程已经两年了，但从来没有学习有关算法的知识，因为以后励志想要成为一名合格的程序员，知道算法在编程中是不可或缺的，但现在太正式的学习又会让自己失去信心，所以网上找到这本书，算是培养一下自己的兴趣吧，这本书特点是图文并茂，风趣易懂。(要求:C语言基础) 我用的编译器：Pelles C

最快最简单的排序(桶排序)

问题：生活中有许多需要处理排序的问题，考试中，评奖学金等等，如何编写一段程序

解决:只需借助一个一维数组就可以解决。
假设:我们编写一个排序 5 个数的大小

  1. 申请一个大小为 11 的数组 int a[11]
  2. 初始化 a[0]~a[10] 都为 0 ,表示没有分数
  3. 处理这 5 个数 ,因为是排序分数 ，利用数组输出特性,将分数的值存在对应的位置，比如 5分 就存在 a[5] 中,并把值改为 1 ，表示出现过的次数
  4. 输出:遍历数组，依次打印，数值>0 的数组多少就打印几次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main(void)
{
	int a[11],i,j,t;
	for(i=0;i<=10;i++)
		a[i]=0;//初始化为0
	for(i=1;i<=5;i++)
	{
		scanf("%d",&t);
		a[t]++;
	}
	for(i=0;i<=10;i++)
		for(j=1;j<=a[i];j++)
			printf("%d",i);
	getchar();
}

这种排序方法我们暂且叫”桶排序”,这个不是正真的桶排序,这个程序好比 11 个桶,编号从 0~10 每出现一个数,就将对应编号的桶加1，然后按顺序将通的编号打印出来，打印的次数为桶中的个数

上面的只接受 10 以内的排序，如果需要更大范围排序，需要修改数组的大小。如何实现从大到小排序？

1
2
3
4
// 只需要将数组从大到小遍历就可以了
for(i=10;i>=0;i--)
	for(j=1;j<=a[i];j++)
		printf("%d",i);

时间复杂度: O(m+n+m+n)
m:桶的数量
n:输入的次数

如果每个数据对应一个名字 这种简单算法就无法进行,这就要用到冒泡排序

(*^▽^*)