本文共 4052 字,大约阅读时间需要 13 分钟。
假设班上只有5 个同学,这5 个同学分别考了5 分、3 分、
5 分、2 分和8 分,现在想从小到大进行排序, 首先我们需要申请一个大小为11 的数组int a[11]。OK,现在你已经有了11 个变量,编号从a[0]-a[10]。刚开始的时候,我们将a[0]~a[10]都初始化为0,表示这些分数还都没有人 得过。例如a[0]等于0 就表示目前还没有人得过0 分,同理a[1]等于0 就表示目前还没有人得过1 分……a[10]等于0就表示目前还没有人得过10 分 下面开始处理每一个人的分数,第一个人的分数是5 分,我们就将相对应的a[5]的值在原来的基础增加1,即将a[5]的值从0 改为1,表示5分出现过了一次,,a[0]~a[10]中的数值其实就是0 分到10 分每个分数出现的次数。接下来,我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。#includeint main(){ int a[11],i,j,t;for(i=0;i<=10;i++)a[i]=0; //初始化为0for(i=1;i<=5;i++) //循环读入5个数{ scanf("%d",&t); //把每一个数读到变量t中a[t]++; //进行计数}for(i=0;i<=10;i++) //依次判断a[0]~a[10]for(j=1;j<=a[i];j++) //出现了几次就打印几次printf("%d ",i);getchar();getchar();//这里的getchar();用来暂停程序,以便查看程序输出的内容//也可以用system("pause");等来代替return 0;}
只需要将for(i=0;i<=10;i++)改为for(i=10;i>=0;i–)就可以实现从大到小排序。
这个算法就好比有11 个桶,编号从0~10。每出现一个数,就在对应编号的桶中放一个小旗子,最后只要数数每个桶中有几个小旗子就OK 了。 如果需要对数据范围在0~1000 之间的整数进行排序,我们需要1001 个桶,(不是1000个)来表示0~1000之间每一个数出现的次数,这一点一定要注意。另外,此处的每一个桶的作用其实就是“标记”每个数出现的次数。最终桶排序的时间复杂度为O(m+n)。还有一点,在表示时间复杂度的时候,n 和m通常用大写字母即O(M+N)。
#includeint main(){ int a[1001],n,i,t;for(i=1;i<=1000;i++)a[i]=0; //初始化scanf("%d",&n); //读入nfor(i=1;i<=n;i++) //循环读入n个图书的ISBN号{ scanf("%d",&t); //把每一个ISBN号读到变量t中a[t]=1; //标记出现过的ISBN号}for(i=1;i<=1000;i++) //依次判断1~1000这个1000个桶{ if(a[i]==1)//如果这个ISBN号出现过则打印出来printf("%d ",i);}getchar();getchar();return 0;}
假设有n个元素m个桶,如果元素值是平均分布的,则每个桶里面平均有n/m个元素,如果对每个桶中的元素进行快速排序那么桶排序的时间复杂度=o(n+log2n-nlog2m) 当m接近n时桶排序的时间复杂度接近o(n)
一种更有效的方法是求出a中的最大元素max和最小元素min,设置桶个数num = (max-min+1)/10+1;然后对a数组从头到尾扫描一遍,把a[i]放入对应的桶B[K](K=(a[i]-min+1)/10)再对这些桶进行排序,最后依次输出每个桶里的元素#define bsize 10 // 每个桶的大小typedef { int data[bsize];//桶中放的元素int count;// 桶中元素个数}BuckType;void BuckSort(int a[], int n){ int min = a[0], max = a[0];for(int i = 0;i < n; i++){ if(a[i] > max)max = a[i];if(a[i] < min)min = a[i]; }num = (max - min +1)/10;//桶个数BuckType* pb=(BuckType*) malloc(sizof(BuckType)*num);memset(0, pb, sizof(BuckType) *num);for(int i = 0;i < n; i++){ k = (a[i] -min +1)/bsize;//将a的所有元素分配到对应桶中(pb+k) ->data[(pb+k)->count] = a[i];//k是桶编号(pb+k)->count++;}int t = 0;for(int i = 0;i < num ;i++){ QickSort((pb+i)->data,0,(pb+i)->count - 1);//单个桶快速排序for(int j = 0;j <(pb+i)->count; j++)a[t++] = (pb+i)->data[j];}free(pb);//释放内存}
上面的算法是基于输入的n个元素平均分布的假设,否则如果所有元素都落在一个桶中就退化成一般的排序了,且适合元素集并不大的情况
将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的
第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。 出牌和赢牌这恰好对应队列的两个操作,出牌就是出队,赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个栈,每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候,依次将牌从桌上拿走,这就相当于出栈。那如何解决赢牌的问题呢?赢牌的规则是:如果某人打出的牌与桌 上的某张牌相同,即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌了呢?最简单的方法就是枚举桌上的每一张牌,当然也有更好的办法:是用一个数组来记录桌上有哪些牌。因为牌面只有1~9,因此只需开一个大小为10 的数组来记录当前桌上已经有哪些牌面就可以了。 初始化时 for(i=1;i<=9;i++) book[i]=0; 如果桌面上增加了一张牌面为2 的牌,那就需要将book[2]设置为1,表示牌面为2 的牌桌上已经有了。当然如果这张牌面为2 的牌被拿走后,需要及时将book[2]重新设置为0,表示桌面上已经没有牌面为2 的牌了。struct card{ int tail;int head;//队头和队尾用来入队和出队int num[100];};struct tablecard { int data[10]; int top;}; int main() { int marked[10] = { 0};struct card c1,c2;struct tablecard tb;c1.tail = c1.head = 1;c2.head = c2.tail = 1;for(int i = 0;i < 6;i++){ //6代表一开始每个人手上六张牌 cin>>c1.num[c1.tail]; c1.tail++;}for(int i = 0;i < 6;i++){ //6代表一开始每个人手上六张牌 cin>>c2.num[c2.tail]; c2.tail++;}for(int i = 0;i < 10; i++)marked[i] = 0;tb.top = 0;int t;while(c1.head < c1.tail && c2.head < c2.tail){ t = c1.num[c1.head];c1.head++;if(marked[t]) { c1.num[c1.tail] = t; c1.tail++; while(tb.data[tb.top] != t) { c1.num[c1.tail++] = tb.data[tb.top]; marked[tb.data[tb.top]] = 0;//!!!!注意,要记得取消标记 tb.top--; }}else { marked[t] = 1;tb.top++;tb.data[tb.top] = t;}t = c2.num[c2.head];c2.head++;if(marked[t]) { c2.num[c2.tail] = t; c2.tail++; while(tb.data[tb.top] != t) { c2.num[c2.tail++] = tb.data[tb.top]; marked[tb.data[tb.top]] = 0;//!!!!注意,要记得取消标记 tb.top--; }}else { marked[t] = 1;tb.top++;tb.data[tb.top] = t;}}if(c1.head != c1.tail){ cout<<"小明!";for(int i = c1.head;i!=c1.tail; i++)cout<
转载地址:http://xxten.baihongyu.com/