快速排序遞歸和非遞歸方法的簡單介紹

基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

實現快速排序的單趟排序中有三種方法：1. 左右指針法；2. 挖坑法；3. 前后指針法

1. 左右指針法：其基本思想就是begin指針指向數組的首元素，begin作用是找大于key的值；end指針指向數組的末尾元素，end作用是找小于key的值；key為基準值此時選擇末尾元素作為基準值（選擇首元素作為基準），那么需要左邊先走也就是begin先移動（那么需要右邊先走也就是end移動）。begin找到大于key的值就和end位置的值交換（end找到小于begin的值就和begin位置的值交換），直到begin和end相遇，相遇后此位置就是key再數組最終有序后的位置。

畫圖舉例：如下圖所示key=8到了正確的位置，將數組分為左右兩部分，然后遞歸調用單趟（第一趟）排序的方法即可。注意：選右（左）邊為基準一定要讓左（右）邊先走，否則會出問題，具體畫圖得知

// 交換兩個數
void Swap(int* q1, int* q2)
{int temp = *q1;*q1 = *q2;*q2 = temp;
}// 單趟 左右指針法
int partionsort1(int* arr, int begin, int end)
{assert(arr);// 以下兩行代碼是三數取中間值解決快速排序最壞的情況的時間復雜度，后面講到了取消注釋即可//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);int keyindex = end; // 選右邊則begin左邊先走反之右邊先走while (begin < end){// begin先走 找大while (begin < end && arr[begin] <= arr[keyindex]) // 不加=號可能會導致死循環{++begin;}// end 找小while (begin < end && arr[end] >= arr[keyindex]){--end;}Swap(&arr[begin], &arr[end]);}Swap(&arr[begin], &arr[keyindex]);return begin;
}

2. 挖坑法：

選擇end位置為初始坑，用key保存end位置的值，begin移動找到大于key的值，將該值放到end處，此時begin處就是新的坑（數據可以被覆蓋）；然后end移動找到小于key的值，將該值放到begin處，此時end處就是新的坑（數據可以被覆蓋）。重復下去直到begin和end相遇。key放到他們相遇后的位置即可

畫圖舉例：

// 方法2 挖坑法--這個方法比較好理解
int partionsort2(int* arr, int begin, int end)
{assert(arr);//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);// 第一個坑，初始坑，end位置就是坑，數據可以被覆蓋int key = arr[end];while (begin < end){while (begin < end && arr[begin] <= key){begin++;}// 左邊的值比key大，將begin的值填到end的坑上，begin位置就形成了新的坑arr[end] = arr[begin];while (begin < end && arr[end] >= key){end--;}// 右邊的值比key小，將end的值填到begin的坑上，end位置就形成了新的坑arr[begin] = arr[end];}// begin和end相遇后就是 這個位置就是坑，也就是key的最終位置arr[begin] = key;return begin;
}

3. 前后指針法：

選擇最后一個位置作為基準值key，prev指針指向首元素的前一個位置，cur指針指向首元素，當cur位置的數據小于key時，并且prev+1不等cur時將prev和cur位置的值互換，然后cur++；不進行互換時cur也++。當cur走到end位置后，只需要將key的值和prev+1位置的值互換即可。

畫圖舉例：

// 方法3 前后指針法
int partionsort3(int* arr, int begin, int end)
{assert(arr);//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);int keyindex = end;int prev = begin - 1;int cur = begin;while (cur < end){if (arr[cur] < arr[keyindex] && ++prev != cur)Swap(&arr[cur], &arr[prev]);cur++;}// 畫圖演示，最后是要將key和prev的下一個位置的數據進行交換，key的左邊才小于key右邊才大于keySwap(&arr[++prev], &arr[keyindex]);return prev;
}

遞歸方法：

利用函數遞歸調用以上三種方法中的其中一種即可：第一調用時，數組被分為了小于key的前半部分和大于key的后半部分，分別在調用函數對這兩部分進行排序即可

void QuickSort1(int* arr, int left, int right)
{assert(arr);if (left >= right)return;int div = partionsort1(arr, left, right);// 排左邊部分 [left,div-1] div [div+1 right]QuickSort1(arr, left, div - 1);// 排右邊部分QuickSort1(arr, div + 1, right);//if (left < right)//{//	int div = partionsort(arr, left, right);//	// 排左邊部分//	QuickSort(arr, left, div - 1);//	// 排右邊部分//	QuickSort(arr, div + 1, right);//}
}

快速排序的缺點：?數據已經有序的情況下每一次都選擇左邊或者右邊作為key，左邊或者右邊剩下很多數據，要繼續排序建棧幀，會導致棧溢出，比如 1w個有序數，就要建1W個棧幀,此時就是最壞的情況。（時間復雜度為 O (n2)）

前面提到三數取中間值的方法就能夠解決最壞的情況，基準值被選在數組中間位置，讓數組能較為均衡地被劃分，快速排序的時間復雜度得以維持在 O (nlogn)。

// 獲得前中后三個數中的中間值，解決快速排序的最壞的情況
int Getmidindex(int* arr, int begin, int end)
{assert(arr);int mid = (begin + end) / 2;if (arr[begin] < arr[mid]){if (arr[mid] < arr[end])return mid;else if (arr[begin] > arr[end])return begin;elsereturn end;}else  // arr[begin] > arr[mid]{if (arr[mid] > arr[end])return mid;else if (arr[end] > arr[begin])return begin;elsereturn end;}
}

優化：待排序的區間小于10的時候使用直接插入排序

// 優化
void QuickSort2(int* arr, int left, int right)
{assert(arr);if (left >= right)return;// 區間大于10if ((right - left + 1) > 10){int div = partionsort3(arr, left, right);// 排左邊部分 [left,div-1] div [div+1 right]QuickSort2(arr, left, div - 1);  // 左遞歸// 排右邊部分QuickSort2(arr, div + 1, right);  // 右遞歸}//區間小于10使用插入排序else{InsertSort(arr + left, right - left + 1);}//if (left < right)//{//	int div = partionsort(arr, left, right);//	// 排左邊部分//	QuickSort(arr, left, div - 1);//	// 排右邊部分//	QuickSort(arr, div + 1, right);//}
}

非遞歸方法：

遞歸的實現，就是給每一個遞歸函數建立函數棧幀，通過壓棧的方式存儲函數的參數。這里使用棧來模擬函數棧幀。

前面已經講到了棧的相關實現代碼，這里就直接使用了：

畫圖理解，下圖畫出了遞歸的區間變化圖，非遞歸只需要將left和right壓入棧中，再取出來即可傳給partionsort即可，只要棧不空，那么就有子區間還是無序狀態，棧空后數組就排序完成。

// 遞歸改非遞歸，1：改循環（斐波那契數列求解）一些簡單的遞歸才能改；2：棧模擬存儲數據
// 非遞歸作用：1：提高效率（建立函數棧幀還是有消耗的，但是對于現代計算機，這個優化微乎其微可以忽略不計）
//           2：遞歸最大缺陷就是，如果棧幀的深度太深，可能會導致棧溢出，因為系統的棧區空間一般不大在M級別，
//			 數據結構棧模擬非遞歸， 數據是存儲在堆區上面的，堆區空間是G級別的
// 快速排序--非遞歸方法--利用棧替代棧區（函數棧幀）
void QuickSortNonR(int* arr, int left, int right)
{assert(arr);Stack st;       // 建棧StackInit(&st); // 初始化棧// 將最開始的區間壓入棧StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){// 數組左區間值int begin = StackTop(&st);  // 取棧頂數據StackPop(&st);              // 出棧// 數組右區間值int end = StackTop(&st);StackPop(&st);int div = partionsort2(arr, begin, end);  // 排序// [begin,div-1] div [div+1,end]// 如果剩下待排序的兩段區間的元素個數大于1個那么就入棧，再取出來排序// 和遞歸一樣先排左區間再排右區間if (div + 1 < end)  // 右區間，相當于右遞歸{StackPush(&st, end);StackPush(&st, div+1);}if (begin < div - 1)  // 左區間，相當于左遞歸{StackPush(&st, div - 1);StackPush(&st, begin);}}StackDetory(&st);
}

結論：

快速排序是一種基于分治思想的高效排序算法，其核心是通過基準值將數組劃分為左右兩部分，遞歸處理直至有序。本文詳細介紹了三種單趟排序實現方法：1)左右指針法通過雙指針交換元素；2)挖坑法通過移動基準值"坑位"；3)前后指針法利用雙指針交替移動。針對遞歸可能導致的棧溢出問題，提出三數取中優化基準值選擇，并建議小規模數據使用插入排序。最后介紹了用棧模擬遞歸的非遞歸實現，有效避免深度遞歸風險。各種方法均附有代碼實現和圖示說明，完整展現了快速排序的優化思路。