一个经典的随机数生成方法以及快排的尝试
昨天没事的时候看了看随机数的产生算法，之前的建模仿真的课程也学过，这次就复习一下： 就目前来看，用的最广泛的应该是线性同余法了，其公式为： a(i+1)=(a(i)*b+c)mod(m) 利用上一次的产生值来得到下一次的随机数,当然此种算法也有很多种改进方式，在此就不仔细讨论了；此时产生的随机数应当是符合[0,1]分布的，若要产生其他分布的随机数应当采用反函数，例如产生一个正态分布的随机数，应当用反函数法，将正态分布的反函数得出，然后将一个符合01分布的数带入求解即可，应当是概率论中比较基本的内容。
在看这个内容的时候搜索到了一个比较有趣的题： 要求产生一个有序的最大值不超过n的m个随机数（不重复）； 这个问题比较有趣，我的第一想法就是先产生随机数然后在排序……对于产生不重复的方法，这种比较简单，就是先初始化一个有序的数组，然后将随机数当做下标，进行交换，这个方法不错其代码为： int a[100]; for(i=0; i<=99; ++i) a[i]=i; for(i=99; i>=1; --i) swap(a[i], a[rand()%i]); 当然我记得改进快速排序的方法时也用到了这个思想，就是产生随机数下标进行交换将原数组随机化一遍；不得不感叹取余数的性质真的很好用…… 回到原来的问题上，原问题是希望产生一个有序的随机数组：那么Kenuth大神给出了这样一种很巧妙的方法：这个方法和上面的有异曲同工的感觉，但是却省去了很多环节，code：
1 for(int i = 0; i < n; i++)
2 {
3 if(rand()%(n-i)<m)
4 {
5 cout<<i<<endl;
6 m--;
7 }
8 }简单有效，四行解决问题！是不是和上面的那段有点相似？一个是先有序，然后从后向前不断的swap ，而这个直接一次性解决；算法的极端情况就是在前面的循环中一直不进入if语句，直到n-i=m时，由于下一次循环中n-i<m，那么根据取余数的性质，后面的循环必然会进入if语句，其实就将m当做上一个程序的下标来看待就好，因为随着i的增大一定会保证会进入if语句的。
最近装好了vim……随手试了一下，根据这个随机数编了个快排试了下（突然发现我每次编的快排的程序都不一样- -是我看太多了方法么……）发现在快排中最后加入冒泡排序对改进的意义不大 ……可能是我用的数组太小了？具体的程序我会push到github上，有个奇怪的地方就是我用g++编译后中用了new申请了新内存，然后去delete时竟然说我double free……这是什么情况……