需求：将一个长度为n的有序数组变为一个随机乱序数组
    （答案在文末）

    方法一：

    1. //伪代码    
    2. for (int i = 0;i < n; ++i)
    3. {
    4.     srand((unsigned)time(NULL));
    5.     swap(arr[i],arr[rand()%n]);
    6. }

    问题：
    1、产生了n^2方种情况，显然不是排列组合中n!的整数倍，所以这种乱序方法是有问题的
    如果不理解，我们下面进行实践

    1.     srand((unsigned)time(NULL));
    2.     vector<int> arr = {4,10,3,5,7,1,6,9,2,8};
    3. //    vector<int> arr = {1,2,3};
    4.     long result[10][10] = {0};
    5.     for (int q=0;q<THOUSAND*THOUSAND;++q)
    6.     {
    7.         for (int i=0;i<arr.size();++i)
    8.         {
    9.             swap(arr[i],arr[rand()%arr.size()]);
    10.         }
    11.         for (int i = 0;i<arr.size();++i)
    12.         {
    13.             for (int j = 0; j<arr.size(); ++j)
    14.             {
    15.                 if (arr[i] == j+1)
    16.                 {
    17.                     ++result[i][j];
    18.                     break;
    19.                 }
    20.             }
    21.         }
    23.     }
    24.     cout<<" p | ";
    25.     for (int i = 0;i<arr.size();++i)
    26.     {
    27.         cout<<setw(6)<<i+1<<" | ";
    28.     }
    29.     cout<<endl;
    30.     for (int i = 0;i<arr.size();++i)
    31.     {
    32.         cout <<setw(2)<< i+1<<" | ";
    33.         for (int j = 0; j<arr.size(); ++j)
    34.         {
    35.             cout<<setw(8)<<result[i][j]*1.0/(THOUSAND*THOUSAND) << " ";
    36.         }
    37.         cout<<endl;
    38.     }
    39.     return 0;

    image.png
    显然概率是有规律的
    image.png
    如果觉得不明显，可以打印长度为3的数组

    方法二：
    因为排列组合有n!种情况，所以产生一个随机数rand()%(n的阶乘)，根据产生的随机数确定排列组合

    问题：
    1、如果n很大，n!必然更大，产生的随机数可能没那么大
    2、根据随机数确定排列组合是一个时间复杂度为O(n^2),且涉及到n!的不优雅的算法

    方法三：
    遍历n次，每次选择随机两个或一个数交换。

    1. int main()
    2. {
    3.     long long num=0;
    4.     srand((unsigned)time(NULL));
    5.     vector<int> arr = {4,10,3,5,7,7,6,4,2,8};
    6.     for (int q=0;q<THOUSAND*THOUSAND;++q)
    7.     {
    8.         sortByBubbing1_0(arr);//排序
    9.         for (int i=0;i<arr.size();++i)
    10.         {
    11.             swap(arr[rand()%arr.size()],arr[rand()%arr.size()]);
    12.         }
    13.         if (arr[0]==2) ++num;
    15.     }
    16.     cout<<num*1.0/(THOUSAND*THOUSAND)<<endl;
    17.     return 0;
    18. }

    产生n^3种情况，错误和方法一类似，输出结果大概为0.2，显然是不对的

    方法四：
    与第二种方法思路类似，但用的是链表实现，且有n个随机数

    1. int main()
    2. {
    3.     long long num=0;
    4.     vector<int> arr = {4,10,3,5,7,1,6,9,2,8};
    5.     long result[10][10] = {0};
    6.     srand((unsigned)time(NULL));  
    7.     for (int q=0;q<THOUSAND*THOUSAND;++q)
    8.     {   
    9.         list<int>::iterator iter;
    10.         list<int> dataListCopy;
    11.         list<int> dataList = {0,1,2,3,4,5,6,7,8,9};
    12.         // 进行乱序
    13.         for (int i=dataList.size();i>0;--i)
    14.         {
    15.             int n = rand()%i;
    16.             int j = 0;
    17.             for (iter = dataList.begin(); iter != dataList.end(); ++iter)
    18.             {
    19.                 if (j==n)
    20.                 {
    21.                     dataListCopy.push_back(*iter);
    22.                     dataList.erase(iter);
    23.                     break;
    24.                 }
    25.                 ++j;
    26.             }
    27.         }
    28.         // 统计结果
    29.         int k = 0;
    30.         for (iter = dataListCopy.begin(); iter != dataListCopy.end(); ++iter)
    31.         {
    32.             for (int j = 0; j<arr.size(); ++j)
    33.             {
    34.                 if (*iter == j)
    35.                 {
    36.                     ++result[k][j];
    37.                     break;
    38.                 }
    39.             }
    40.             ++k;
    41.         }
    42.     }
    43.     // 输出结果
    44.     cout<<" p | ";
    45.     for (int i = 0;i<arr.size();++i)
    46.     {
    47.         cout<<setw(6)<<i+1<<" | ";
    48.     }
    49.     cout<<endl;
    50.     for (int i = 0;i<arr.size();++i)
    51.     {
    52.         cout <<setw(2)<< i+1<<" | ";
    53.         for (int j = 0; j<arr.size(); ++j)
    54.         {
    55.             cout<<setw(8)<<result[i][j]*1.0/(THOUSAND*THOUSAND) << " ";
    56.         }
    57.         cout<<endl;
    58.     }
    59.     return 0;
    60. }

    image.png

    方法五：
    通过思考方法一与方法四，我们发现只要小小的修改一下方法一就能达到方法四的目的（后来我才了解到这是knuth洗牌算法）

    1. // 将数组的头部看成是长度为i+1的原链表，将数组的尾部看成是长度为n-i-1的一个链表，
    2. // 每次从头部中随机选一个元素插入到尾部链表的头部，
    3. for (int i=arr.size()-1; i > 0 ;--i)
    4. {
    5.     swap(arr[i],arr[rand()%(i+1)]);
    6. }

    image.png

    答案虽然重要，但更重要的是思考的过程，它能让我们成长。

    点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。