IT评测·应用市场-qidao123.com

标题: C++ 由快排学习到的的随机数等知识 [打印本页]

作者: 莱莱 时间: 2022-9-17 08:37
标题: 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

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)