用游戏串起程序员的基本功（二）
2004-03-23■作者：潇潇■出处： YESKY
第一篇我们用数组实现了洗牌的步骤。当然还有其他的方法。这也就是编程的带给我们的乐趣——灵活，自由。只要你想不得到，没有你做不到的。
今天我们就来实现第二步。掷色子，发牌。
掷色子的问题，其实很简单，但涉及到动画制作的原理。所以我们先来补充些这方面的知识。
我们知道，人的视觉都有一种现象，比如当你在黑暗中看灯泡时，突然灯泡熄灭了，但灯泡发光的影像还会在我们眼前停几秒钟，这就是我们熟知的“视觉暂留效果”。我们所看到的电视、电影，包括我们说熟知的flash，director等动画制作软件，都是依赖这个效果才实现的。当我们在高速状态下（一般是每秒24帧），按一定的顺序切换内容相近和连贯的一组图片时，我们看到的不是一张张单独的图片影像，而是一段连贯的动画。
根据这个原理。我们掷色子的动画也就很容易实现了。只要我们快速的变换不同点数的色子6个面，就会让人觉得好象是真实的转动着的色子了。你不用担心，运行速度的问题，只要你的机子能看vcd，一般都没问题。先看看下面的代码框架：
void zhisaizi（）
{
int i；
i= （int）5*rand（）+1；
switch（i）
case 1：
//载入第一张图片
case 2：
//载入第二张图片
case 3：
。。。。。。//省略中间过程
case 6：
//载入第六张图片
}
至于怎样载入和现实图像不是我们本篇的主要内容，大家可以学习《windows程序设计》这本书。
对于发牌的问题，我想大家应该不会在有问题了。这里我只给出代码，其中有详细的注释，就不解释了。下面是代码：
int apai[13]，bpai[13]；//apai，bpai分别代表两玩家手中的牌，如果你做的是四个人//的麻将，可你在自由扩展
void fapai（）
{
int a，b；
int i；//i代表发牌的起始位置
if（（i/2）= =0）//是否为偶数
apai[a++]=pai[i++]； //双数牌发给a玩家
else
bpai[b++]=pai[i++]；//单数牌发给b玩家
}
下面是我们本篇要讲的重点：就是在玩家都拿到牌之后，我们需要按顺序摆放好牌。这里我们会更加深入的谈到数据结构方面的一些知识，希望大家用心。
对于这个问题实质上也就是排序的问题。我们前面用136个整型数来代表136张牌，可以用1~136分别表示1~9万，1~9条，1~9饼，以及东南西北红中发财，也可以用1~39中的个位数分别对应着和他相等的1~9万，如3、13、23、33分别代表四张3万。其他以此类推。剩余的数字来表示东南西北红中发财。这个就可以由自己决定了。在此我们选择第一种方法来描述问题。
那么就请怎样排序呢?最容易想到的方法是：取得一个数，和他前面的所有数比较，直到找到一个前面的数比它小，后面的数比他大的位置，并将其放入其中。再取得下一个数，继续上面的步骤。
示例如下：
8 7 4 3 6 1 //是要排序的数值
7 8 4 3 6 1 //第一次，取得7，小于前面的8，交换位置
7 4 8 3 6 1 //第二次，取得4，小于前面的8，交换位置
4 7 8 3 6 1 //第三次，小于再前面的7，交换位置
4 7 3 8 6 1 //第四次，取得3，小于前面的8，交换位置
4 3 7 8 6 1 //第五次，小于再前面的7，交换位置
3 4 7 8 6 1 //第六次，小于再前面的4，交换位置
3 4 7 6 8 1 //第七次，取得6，小于前面的8，交换位置
3 4 6 7 8 1 //第八次，小于再前面的7，交换位置
3 4 6 7 1 8 //第九次，取得1，小于前面的8，交换位置
3 4 6 1 7 8 //第十次，小于再前面的7，交换位置
3 4 1 6 7 8 //第十一次，小于再前面的6，交换位置
3 1 4 6 7 8 //第十二次，小于在前面的4，交换位置
1 3 4 6 7 8 //第十三次，小于再前面的3，交换位置
我们把这种方法叫做“插入排序法”。下面是源代码。
void paixu （）// 用插入排序法
{
for (int i = 1; i <=13; i++)
{
int temp = apai[i];//取得一个数
int j；
for ( j = i; j > 0 && temp < apai[j - 1]; j--) //和他前面的每一个数进行比较，
apai[j] = apai[j - 1]; //如果这个数小于她前面的数就交换
apai[j] = temp;//插入到正确位置
}//end for
}//end
我们先来分析一下这种算法。可以看到，为了找到合适的插入位置，我们要用取得的数值与他前面的所有数值进行比较，并将进行多次的交换位置。尤其是当较小的数值放得越靠后时，交换到合适的位置所需的时间越长，如示例中的6和1，位置都靠后且相邻，但6放置到合适的位置只用了两步，而1放置到合适的位置却用了五步。
有没有其他的方法呢？针对比较次数和交换次数较多，我们可以用另一种“折半插入排序法”。基本思路是：为了减少比较的次数，我们不用每个数都比较，而是先找到所取得的数值在数组中的位置，并找到它前面已排好顺序的数组的中间的一个数值，比较两数，如果取得的数值大，就与後面的数值的中间数值比较，一直下去，直到找到合适的位置；同理如果所取得的数值小，就与前面的数值的中间数值比较，一直下去，直到找到合适的位置。
下面是示例：
8 7 4 3 6 1 //是要排序的数值
7 8 4 3 6 1 //第一次，取得7，小于前面的8，交换位置
7 4 8 3 6 1 //第二次，取得4，小于前面的8，交换位置
4 7 8 3 6 1 //第三次，小于再前面的7，交换位置
3 4 7 8 6 1 //第四次，取得3，小于前面的数组（4 7 8）中的中间数值7比较，小于7，所以比较数组（4 7）中间数值4，大于4，并交换到合适位置
3 4 6 7 8 1 //第五次，取得6，小于前面的数组（3 4 7 8）中的7，再与再靠前的数组（3 4 7）中间值4比较，大于4，交换位置
1 3 4 7 8 6 //第六次，取得1，小于再前面的数组（3 4 6 7 8）中间值6，再与数组
（3 4 6）中间值4比较，小于4，最后与数组（3 4）中间值3 比较，
小于3，交换位置
很明显这种方法的减少了比较的次数，但交换次数仍没减少。下面是其代码：
void paixu（）//用折半排序法
{
for (int i = 1; i < =13; i++)
{
int temp = apai[i]; //取得数值
int low = 0, high = i - 1;//low，high，分别表示比较范围的上下限
while (low <= high)//折半查找
{
int mid = (low + high) / 2; //取得中间位置
if ( temp < apai[mid]) //如果小于中间位置的值
high = mid - 1; //从新确定下限
else //如果大于中间位置的值
low = mid + 1; //从新确定上限
}//end while
for (int j = i - 1; j >= low; j--)
apai[j + 1] = apai[j]; //记录后移
apai[low] = temp; //插入到合适位置
}//end for
}//end
