- 起：
力扣的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);
int i(L);
while (i < more) {
if (nums[i] < nums[R]) {
swap(nums[++less], nums[i++]);
}
else if (nums[i] > nums[R]) {
swap(nums[i], nums[--more]);
}
else
i++;
}
swap(nums[more], nums[R]);
return new int [2]{ less, more+1 };
}
void process(vector<int>& nums, int L, int R) {
if (L < R) {
// cout<<"L ="<<L<<"\t R="<<R<<endl;
swap(nums[getrd(L,R)], nums[R]);
int *p = Mypartition(nums,L,R);
process(nums, L, p[0]);
process(nums, p[1], R);
}
}
vector<int> sortArray(vector<int>& nums) {
process(nums, 0, nums.size()-1);
return nums;
}
};
标签：return,nums,int,C++,快排,32753,swap,随机数 From： https://www.cnblogs.com/xhzg/p/16630883.html