x洗牌算法

A. C语言 洗牌算法

/*洗牌程序:用任何语言,随机分配52张扑克牌到52个位置上,每个位置只容许放一张牌
用1-13表示红心A--K
14-26表示黑桃A,2,3-,Q,K
27-39表示方块A,2,3-,Q,K
40-52表示黑桃A,2,3-,Q,K
也就是生成1-52不重复的随机数，放到数组中*/

#include<iomanip.h>
#include<stdlib.h>
#include<time.h>

const int N=52;
static int a[N];

int create(int n)
{
return (1+rand()%52);
}

int main()
{
int i,j;
srand(time(0));
for(i=0;i<N;++i)
{
a[i]=create(N);
for(j=0;j<i;++j)
{
if(a[j]==a[i])
{
a[i]=(a[i]+1)%52;
}
}
cout<<setw(5)<<a[i];
}
cout<<endl;
return 0;
}

B. 随机洗牌：哪一种算法是正确的

几乎所有的程序员都写过类似于“洗牌”的算法，也就是将一个数组随机打乱后输出，虽然很简单，但是深入研究起来，这个小小的算法也是大有讲究。我在面试程序员的时候，就会经常让他们当场写一个洗牌的函数，从中可以观察到他们对于这个问题的理解和写程序的基本功。 在深入讨论之前，必须先定义出一个基本概念：究竟洗牌算法的本质是什么？也就是说，什么样的洗牌结果是“正确”的？ 云风曾经有一篇博文，专门讨论了这个问题，他也给出了一个比较确切的定义，在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。 第一个洗牌算法：随机抽出一张牌，检查这张牌是否被抽取过，如果已经被抽取过，则重新抽取，直到找到没被抽出过的牌，然后把这张牌放入洗好的队列中，重复该过程，直到所有的牌被抽出。 大概是比较符合大脑对于洗牌的直观思维，这个算法经常出现在我遇到的面试结果中，虽然它符合我们对于洗牌算法的基本要求，但这个算法并不好，首先它的复杂度为O(N2)，而且需要额外的内存空间保存已经被抽出的牌的索引。所以当数据量比较大时，会极大降低效率。