- 起：
力扣的912题 数组排序 ，想着先用快速排序来写写，在实际用c++编写的时候，有一些之前没注意到的细节问题造成了一些麻烦。
- 快排思想
每次以数组最后一个数为基准，按照波兰国旗问题对数组进行分层（partition）。假设最后一个数为P，则将数组分为小于P、等于P、大于P的3层。之后对小于P和大于P的层进行此过程的迭代。迭代完成后，目标数组即排列完成。
- 问题：最坏的结果的O(n^2)，因为每次最后一个数当成分层基准，最坏的情况是左右两层极度不平衡
- 改进：引入随机数，每次进行分层之前，随机将数组前面的一个数与最后一个数P进行swap，这样分层就成了一个随机事件。在数学证明中，可证明时间复杂度收敛于0(N*LogN)。
- C++中的随机数
在c++中，获取随机数一般广为人知的方法是 rand() ，但是这种方法获得的随机数是伪随机数，其原理是从一个已经确定了的序列中按顺序返回整数。
在直接使用 rand()时，默认的 srand(1)。srand可以认为是种子。
只使用rand()时
int main() { for (int i = 0; i < 10; i++) { cout << rand() << "\t"; } return 0; }
输出结果（因电脑而异）：
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
你每次运行，答案和该结果都一致，这是因为种子没变，永远输出的是该序列前十个数字。
所以有一个思路就是改变种子，想让每次运行的种子发生变化，那么就想到了时间，时间是每秒都在变化的，可以让时间来充当种子参数
int main() { srand((int)time(NULL)); // #include<ctime> for time() for (int i = 0; i < 10; i++) { cout << rand() << "\t"; } return 0; }
输出结果：
31937 9951 11817 1295 252 30339 22649 12202 9420 16246
与之前结果不同了。似乎这达到了我们获取真随机数的目的。但是依旧有一个问题，那就是time 是以秒为单位的，如果你的项目要在一秒之内调用多次随机数呢？这样一来，种子在这一秒之内是不会发生变化的。
int getrd_1() { srand((int)time(NULL)); // #include<ctime> for time() return rand(); } int main() { for (int i = 0; i < 10; i++) { cout << getrd_1() << "\t"; } return 0; }
输出结果：
32753 32753 32753 32753 32753 32753 32753 32753 32753 32753
果然是一样的，因为这十次调用都是在1秒之内。
这种情况下，可以使用random_device 来生成真随机数
int getrd(const int &min, const int&max) {//范围 [min,max) std::random_device rd; //#include<random> for std::random_device return min + rd() % max; } int main() { for (int i = 0; i < 10; i++) std::cout << getrd(0, 10) << "\t"; return 0; }
输出结果：
3 0 0 9 7 8 5 4 9 2
达到了我们预期的要求。
但是，需要注意，这个实现要看你的库支持不支持，如果不支持，将继续使用伪随机数发生器。可以通过调用random_device的成员函数 entropy()来查看熵，如果是伪随机发生器，熵恒为零
- swap
//通过一个临时变量来储存b的值，完成交换 void swap(int &a, int &b) { int tmp(b); b = a; a = tmp; } //通过异或^来完成交换 void swap(int &a, int &b) { if (a == b) return; a = a ^ b; b = a ^ b; a = a ^ b; }
第一种交换司空见惯了，第二种则用到了位操作 异或 ^ 的性质：
a ^ 0 等于 a a ^ a 等于 0
满足结合律，交换律
因此:
第一句：a = a ^ b ； 第二句：b = a ^ b，此时 b 等于 a^b^b，结合性质 结果是 a ； 第三句 ： a = a ^ b ，此时 a等于 a ^ b ^ a，结果是b ，交换完成
需要注意的是，如果a 与 b 的地址相同 则 a^b 等于0。
最后贴上我的快排:
class Solution { private: void swap(int& a, int& b) { if (a == b) return; a = a ^ b; b = a ^ b; a = a ^ b; } int getrd(const int &min,const int& max) { random_device rd; return min + rd() % (max - min); } public: //快排 int* Mypartition(vector<int>& nums, int L, int R) { int less(L - 1), more(R); in