標題：[數據結構] 基于交換的排序 冒泡排序&&快速排序
@水墨不寫bug
（圖片來源于網絡）?
目錄
（一）冒泡排序
優化后實現：
（二）快速排序
I、實現方法：?
（1）hoare法
hoare法實現快排：
?（2）挖坑法
挖坑法實現：
（3）雙指針法?
雙指針法實現：?
?II、快速排序復雜度分析：
比較完備的快速排序實現如下：
正文開始：
（一）冒泡排序
?
時間復雜度：O（N^2）
空間復雜度：O（1）
特點：數組接近有序時，可通過優化來提高效率。
穩定性：穩定
冒泡排序：
? ? ? ? 基本思想：大數下沉，小數上浮。
? ? ? ? 實現思路：從內循環到外循環，從一趟到多趟。
????????冒泡排序通過兩層循環來實現，內層循環實現其中的一趟遍歷，在一趟的遍歷中，需要注意要控制好左右區間邊界，冒泡排序的實現方式是多樣的，無論用何種實現方式，最主要的是控制好邊界，以及內外層循環的銜接；以下是一種冒泡排序的寫法：
void BubbleSort(vector<int>& nums) {int n = nums.size();for (int j = 0; j < n - 1; ++j){for (int i = 0; i < n - 1 - j; ++i){if (nums[i] > nums[i + 1]){::swap(nums[i], nums[i + 1]);}}} }優化：
? ? ? ? 如果在一次遍歷的過程中，沒有進入if（）交換，這已經說明數組已經有序，可以直接停止排序。
優化后實現：
void BubbleSort(vector<int>& nums) {int n = nums.size();for (int j = 0; j < n - 1; ++j){int ex = 0;for (int i = 0; i < n - 1 - j; ++i){if (nums[i] > nums[i + 1]){ex = 1;::swap(nums[i], nums[i + 1]);}}if (ex == 0)break;} }
（二）快速排序
時間復雜度：O（NlogN）
空間復雜度：
特點：當數據接近有序，比如逆序的時候；或者選取的key在數據中大量存在時，快速排序時間復雜度會退化為O（N^2），這是相當嚴重的缺陷。
穩定性：不穩定。
????????快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法。
????????基本思想：任取待排序元素序列中的某元素（記為key）作為基準值，按照key值將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值key，右子序列中所有元素均大于基準值key。然后遞歸，左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
? ? ? ? 本質就是將數組根據key值分為兩部分，一部分比key大，一部分比key小。對于每一個部分，再次進行如上操作，直到數組不可再分為止。這就是遞歸實現的淺層次的直觀理解。但是遞歸不是本文的重點，關于遞歸，我會在后面與你分享。?
I、實現方法：?
（1）hoare法
? ? ? ? hoare法是快排的提出者hoare提供的方法，是一種經典的實現方法。
實現原理：
? ? ? ? 定義兩個下標：左下標L? 和? 右下標R；
? ? ? ? 隨機選取一個key值，習慣上我們選擇區間的最左側的元素為key；
? ? ? ? 讓右下標先走，向左尋找比key小的值，找到后停下來：
?停下來后：
?左下標再向右尋找比key大的值，找到后停下來：
此時，交換兩個下標對應的值：
?
接下來繼續執行上述步驟（R先走），我展示關鍵步驟：
?兩下標找到要求目標并交換：
直到遇到特殊情況：兩下標相遇
?
?這時停止停止循環，將最左側元素與相遇處的元素交換位置：
即可完成一次二分。????????接下來，對于左右區間再次進行上述操作，直到區間不可再分為止。
但是如何保證相遇處的值一定小于key呢？
對于相遇這個事件，有且僅有兩種情況：
只可能是R向左移動遇到L；或者是L向右移動遇到R；
????????（1）R向左移動遇到L：有兩種可能情況
? ? ? ? ? ? ? ? ? ? ? ? a，第一次R由于沒有找到比key小的值，直接一路向左遇到left，此時left就是key，然后執行自己與自己交換：此時相遇的位置的值就是key本身。
? ? ? ? ? ? ? ? ? ? ? ? b，第一次之后R向左遇到L，你要想清楚，在此之前L停止的地方是被交換后的原先R的值（它是比key小的）；在這樣的前提條件下，R向左移動與L相遇了，說明R沒有找到小于key的元素，與L相遇后指向L的比key小的值。
? ? ? ? （2）L向右移動遇到R
? ? ? ? ? ? ? ? ? ? ? ? R先走，在找到比key小的位置停下，在此前提下，L向右移動與R相遇了，L指向R的比key小的值。
hoare法實現快排：
void QuickSort(vector<int>& nums,int left,int right) {//遞歸出口，此時區間不存在或者只有一個值if (left >= right)return;//保存左右下標的值，便于在遞歸時找到原來的區間邊界int begin = left, end = right;//keyi來記錄左區間的下標int keyi = left;while (left < right){//右下標先走，找小while (left < right && nums[keyi] <= nums[right]){--right;}//左區間再走，找大while (left < right && nums[left] <= nums[keyi]){++left;}::swap(nums[left], nums[right]);}//此時一趟完畢，將key與相遇位置交換::swap(nums[left], nums[keyi]);keyi = left;//更新keyi//遞歸左右區間QuickSort(nums, begin, keyi);QuickSort(nums, keyi+1, end); }
?（2）挖坑法
實現原理：
? ? ? ? 由于左邊有坑，所以右下標先走。
? ? ? ? 找小，找到后停下來，將找到的值放在坑中，R的位置就成為了新的坑：
此時坑在右邊，左邊下標先走，找大：
找到后交換，左邊又成為新的坑。
以此類推，直到左右相遇，相遇的位置一定是坑，此時將key放到坑中，完成單趟：
依然是左邊都是比6小，右邊都是比6大，說明沒有錯誤。
挖坑法實現：
void QuickSort_(vector<int>& nums, int left, int right) {if (left >= right)return;int begin = left, end = right;int key = nums[left];//記住key的值int hole = left;//開始挖坑while (left < right){//右先找比key大的while (left < right && nums[right] >= key)right--;//找到后，填坑，然后挖新坑nums[hole] = nums[right];hole = right;//左找比key小的while (left < right && nums[left] <= key)left++;//找到后，填坑，然后挖新坑nums[hole] = nums[left];hole = left;}//此時相遇了，把key值放在坑里nums[hole] = key;QuickSort_(nums,begin,hole);QuickSort_(nums,hole + 1,end); }
（3）雙指針法?
?
// 設置前指針prev，指向首元素，遍歷指針cur指向第二個元素，
// 接下來cur開始找小，如果沒找到小，就一直往前走；//如果找到小的了，就先停下來，然后prev往前走一步，再和cur交換值，然后cur繼續向后，重復上述步驟，
// 最后cur走出數組后，循環終止！此時prev指向的位置和keyi的位置交換。我們詳細看一下過程：
????????
雙指針法實現：?
void QuickSort__(vector<int>& nums, int left, int right) {if (left >= right)return;int begin = left, end = right;int prev = left;int cur = left + 1;int keyi = left;while (cur <= right)//cur走出數組循環停止{//cur一直在走，如果遇到比keyi小的，就停下來等perv走一步后交換，再接著走if (nums[cur] < nums[keyi] && ++prev != cur)swap(nums[prev], nums[cur]);cur++;}//cur出去后，prev的值和keyi交換swap(nums[keyi], nums[prev]);QuickSort__(nums,left,keyi);QuickSort__(nums,keyi+1,end);}
?II、快速排序復雜度分析：
? ? ? ? 傳統的快速排序在處理一些極端問題時會顯得無力，接下來我們就來討論這些極端情況，并且給出應對極端情況的方法：
1.對于選擇key不合適的問題：
? ? ? ? 在數組元素接近逆序的時候，由于我們總是在區間的最左側選取key，如果數組接近逆序，這時選取的key無法有效的將數組分為兩個等大的數組，這就導致一次只能排序一個元素，這導致快速排序的復雜度會退化為O（N^2）,這就需要我們不能隨便取key。可以通過隨機數法在區間內隨機取一個元素作為key即可。
2.關于選擇key大量出現的問題：
? ? ? ? 如果key大量出現，也會導致上述的情況，一次只能排序一個數，所以我們不能隨便分區間，這就要求我們將數組分為三部分，左側區間都小于key，中間區間則是數值等于key的元素，右側區間是大于key的數值。
比較完備的快速排序實現如下：
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}void qsort(vector<int>& nums,int l,int r){//遞歸出口if(l >= r) return;//數組分三塊int key = GetRandom(nums,l,r);int cur = l,left = l-1,right = r+1;while(cur < right){if(nums[cur] < key) swap(nums[++left],nums[cur++]);else if(nums[cur] == key) cur++;else swap(nums[--right],nums[cur]); }//遞歸排序子區間qsort(nums,l,left);qsort(nums,right,r);}int GetRandom(vector<int>& nums,int left,int right){return nums[ rand() % ( right - left + 1 ) + left];}
};?完~
未經作者同意禁止轉載
