《啊哈算法》笔记—1
第一章 排序
第一节 桶排序
问题:满分为十分,现要把五个同学的分数5分、3分、5分、2分、8分从高到低排序,要如何排?
- 思路:利用数组 int a [ ] 即可,从0~10开始算起,将分数出现的次数赋值于数组当中。这样以上五个同学a[0]— a[10]的值分别为:
a[0] = 0 不打印 a[6] = 0不打印
a[1] = 0 不打印 a[7] = 0不打印
a[2] = 2 打印2 a[8] = 1 打印1
a[3] = 1 打印1 a[9] = 0不打印
a[4] = 0 不打印 a[10] = 0不打印
a[5] = 2 打印55 a[11] = 0不打印
最终输出“2,3,5,8”的结果
完整的代码:
#include <stdio.h>
int main()
{
int a [11],i,j,t;
for(i=0;i<=10;i++)
a [i]=0;//初始化为0
for(i=1;i<=5;i++)//循环输入5个数
{
scanf("%d",&t);//把每个数读到变量中去
a[t]++; //进行计数
}
for(j=1;j<a[i];j++)//出现几次就打印几次
get char();get char();
//这里一个是用来暂停程序,查看输出内容;
//也可用system pause()来代替;
return 0;
}
对0~1000的几个数据按照从小到大的顺序排序,注意从大到小则需改成:for(i=1000;i>0;i--)
#include <stdio.h>
{
int a [1001],i,j,t;
for(i=0;i<1001;i++)
a[i]=0;//初始化为0
for(i=1;i<=1001;i++)//循环计数
{
scanf("%d",&t);//把每个数读到变量中去
a[t]++;//进行计数
}
for(j=1;j<=a[i];j++)//出现几次就输出几次
get char();get char();
return 0;
}
- 关于时间复杂度的问题
以上述例子为准,整个排序算法一共执行了m+n+m+n次,O(m+n+m+n)=O(2*(m+n)),常数可以忽略不计,则最终的时间复杂度为O(m+n),通常写为大写O(M+N)
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。