《Cracking the Coding Interview》——第18章：难题—

《Cracking the Coding Interview》——第18章：难题——题目2

2014-04-29 00:59

题目：设计一个洗牌算法，效率尽量快点，必须等概率。

解法：每次随机抽一张牌出来，最后都抽完了，也就洗好了。时间复杂度O(n^2)，请看代码。

代码：

 1 // 18.2 shuffle a deck of 52 cards, it must be perfect random.
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <ctime>
 5 #include <vector>
 6 using namespace std;
 7 
 8 void printCards(const vector<int> &cards)
 9 {
10     int i;
11     int n = (int)cards.size();
12     const int col = 8;
13     
14     for (i = 0; i < n; ++i) {
15         printf((i % col == col - 1 ? "%4d
" : "%4d "), cards[i]);
16     }
17     printf("
");
18 }
19 
20 void shuffleCards(vector<int> &cards)
21 {
22     vector<int> v;
23     
24     v = cards;
25     int i, j;
26     int n, n0;
27     int idx;
28     
29     n0 = n = (int)cards.size();
30     for (i = 0; i < n0; ++i) {
31         idx = rand() % n;
32         cards[i] = v[idx];
33         --n;
34         for (j = idx; j < n; ++j) {
35             v[j] = v[j + 1];
36         }
37     }
38     
39     v.clear();
40 }
41 
42 int main()
43 {
44     srand((unsigned)time(NULL));
45     vector<int> cards;
46     int i;
47     const int n = 52;
48     
49     cards.resize(n);
50     for (i = 0; i < n; ++i) {
51         cards[i] = i;
52     }
53     
54     shuffleCards(cards);
55     printCards(cards);
56     
57     return 0;
58 }