• 起：

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

912. 排序数组 - 力扣（LeetCode）

 

 

 

• 快排思想

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

1. 　　问题：最坏的结果的O(n^2)，因为每次最后一个数当成分层基准，最坏的情况是左右两层极度不平衡
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;
    }
};