【算法学习笔记】桶排序的实现（两种形式）+习题：出牌游戏

怼烎@ 2022-10-08 14:26 10阅读 0赞

## 法1引入： ##

假设班上只有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 分每个分数出现的次数。接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下。

#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); //把每一个数读到变量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)。

## 稍加改动：用桶排序去重 ##

#include <stdio.h>
    int main()
    { 
    int a[1001],n,i,t;
    for(i=1;i<=1000;i++)
    a[i]=0; //初始化
    scanf("%d",&n); //读入n
    for(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;
    }

## 法2 ##

假设有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<<c1.num[i];
    }
    if(c2.head != c2.tail)
    { 
      cout<<"小王！";
      for(int i = c2.head;i!=c2.tail; i++)
    cout<<c1.num[i];
    }
    }