关于快速排序选择随机数做标志元素程序中，生成随机数代码问题。

Question

1

<br>

如图，贴出来的代码是老师的快速排序算法中随机指定标志元素的实现方式。但是我有一个疑问：为什么不将srand（time（NULL））这条代码放在quicksort()函数里而不是直接放在-parition()函数里，会有所不一样吗？

Answer 1

liuyubobobo 2017-11-09 14:07:30

在这个例子里，从最后的结果看，没有不一样，都完成了随机化的快排。但是从代码本身调用的角度看，有问题。

这里的关键是，设置种子是用来启动一个随机序列的，而不是启动一个随机数的。

举个简单的例子，生成一个具有n个元素的范围在[rangeL, rangeR]的随机序列，我们可以这样写：

1 2 3 4 5 6 7

int* generateRandomArray1(int n, int rangeL, int rangeR){     srand(time(NULL));     int* arr = new int[n];     for(int i = 0 ; i < n ; i ++)         arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;     return arr; }

也可以这样写：

1 2 3 4 5 6 7 8

int* generateRandomArray2(int n, int rangeL, int rangeR){     int* arr = new int[n];     for(int i = 0 ; i < n ; i ++){         srand(time(NULL));         arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;     }     return arr; }

注意，这里第一种写法就对应了我在课程中的思路，第二种写法对应了你的思路。

但是有的时候，为了debug方便，我们有一个需求，就是要在随机函数中可以传入随机种子，这样一来，每次传入的随机种子相同，则能产生出相同的随机序列。在这种需求下，我的写法改成了这样：

1 2 3 4 5 6 7

int* generateRandomArray1(int n, int rangeL, int rangeR, int seed){     srand(seed);     int* arr = new int[n];     for(int i = 0 ; i < n ; i ++)         arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;     return arr; }

注意，我们多了一个叫seed的参数，在srand中使用用户传来的seed。

相应的，你的写法变成这样：

1 2 3 4 5 6 7 8

int* generateRandomArray2(int n, int rangeL, int rangeR, int seed){     int* arr = new int[n];     for(int i = 0 ; i < n ; i ++){         srand(seed);         arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;     }     return arr; }

可以试试看，在这种情况下，不管你传入的seed是什么，你的写法都将生成一个有n个相同元素的数组。这个相同元素是什么是靠seed启动的。但是每次都使用同样的seed启动，则会不停地生成同一个元素。

随机数的生成本身是一个比较高级的话题，对这个话题感兴趣的话，可以在网上搜索自学一下随机数的生成算法。不过在这里，了解seed的设置本身是为了启动一个随机序列而不是一个随机数的，就够啦：）

• 提问者 奔跑的小女子 #1

  非常感谢！