C++ 由快排学习到的的随机数等知识

• 起：
  

力扣的912题 数组排序 ，想着先用快速排序来写写，在实际用c++编写的时候，有一些之前没注意到的细节问题造成了一些麻烦。
912. 排序数组 - 力扣（LeetCode）

 
 
 

• 快排思想
  

　　每次以数组最后一个数为基准，按照波兰国旗问题对数组进行分层（partition）。假设最后一个数为P，则将数组分为小于P、等于P、大于P的3层。之后对小于P和大于P的层进行此过程的迭代。迭代完成后，目标数组即排列完成。

• 　　问题：最坏的结果的O(n^2)，因为每次最后一个数当成分层基准，最坏的情况是左右两层极度不平衡
  
• 　　改进：引入随机数，每次进行分层之前，随机将数组前面的一个数与最后一个数P进行swap，这样分层就成了一个随机事件。在数学证明中，可证明时间复杂度收敛于0(N*LogN)。
  

• C++中的随机数
  

　　在c++中，获取随机数一般广为人知的方法是 rand() ，但是这种方法获得的随机数是伪随机数，其原理是从一个已经确定了的序列中按顺序返回整数。
　　在直接使用 rand()时，默认的 srand(1)。srand可以认为是种子。
　　　　只使用rand()时
[code]int main() {    for (int i = 0; i < 10; i++) {        cout