简单算法(一)

从极客学院 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:输入的次数

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