- 起：
力扣的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()時
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; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505481.html
標籤：其他
上一篇：使用SLF4J和LOGBACK （二 ：核心組件 ）
下一篇：django中的模板層簡介