這裡給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 最近在研究一個基於TP6的框架CRMEB，這裡分享下我的開發心得 首先要獲取原始項目文件 這裡是git地址 https://gitee.com/ZhongBangKeJi/CRMEB.git 項目環境的要求為Apache、MySQL、PH ...
- 起：
力扣的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; } };
