🔶 一、快速排序（Quick Sort）

📌 基本思想：

分而治之：

????????每次從數組中選一個“基準”（pivot），把比它小的放左邊，大的放右邊。

• 對左右子數組遞歸排序。

🧠 排序過程：

1. 選擇一個基準（如第一個或最后一個元素）。

2. 使用雙指針或 Lomuto/Hoare 分區法將數組分為左右兩部分。

3. 對左右子數組遞歸調用快速排序。

?? 時間復雜度：

?? 穩定性：

不穩定排序

? 優點：

• 速度快：在大多數實際情況下性能極佳。

• 原地排序：不需要額外內存。

• 幾乎是排序算法中的性能王者（除非你特別追求穩定性）。

? 缺點：

• 最壞情況下可能退化為 O(n2)。當我們選擇的基準為最大元素或者最小元素

• 遞歸層數深時可能棧溢出（需優化）。

• 算法思維：

• 選擇基準值，利用雙指針遍歷數組，將比基準值小的放置左邊，比基準值大的放置右邊。

• 思維導圖：

代碼實現：

?int PartSort(int* arr,int left,int right){assert(arr);int key_index = right;int begin = left;int end = right;while (begin< end){ while(begin < end && arr[begin] <= arr[key_index]){begin++;}while(begin < end && arr[end] >= arr[key_index]){end--;}Swap(&arr[begin],&arr[end]);}Swap(&arr[key_index],&arr[begin]);return begin;
}
void QuickSort(int* arr,int left,int right){assert(arr);if(left<right){int div = PartSort(arr,left,right);QuickSort(arr,left,div-1);QuickSort(arr,div+1,right);}
}

注意??：

? ? ? ? 快速排序如果選擇的基準值（key）如果為序列中的最大最小元素時，需要開辟非常多的棧，非常容易導致棧溢出，以及時間復雜度也會更高，最高為。所以為此要避免選取最大元素或者最小元素，比如有序序列時。

快速排序改進方法：

? ? ? ? “三數取中”：保證不要選到最小或者最大，讓有序時最為優；

思維導圖：

??代碼實現：

//三數取中優化
int get_midindex(int*arr,int left,int right){assert(arr);int mid = left+(right-left)/2;if(arr[left]>= arr[mid] && arr[left]<=arr[right] || arr[left]<= arr[mid] && arr[left]>=arr[right]){return left;}else if(arr[mid]>= arr[left] && arr[mid]<=arr[right] || arr[mid]<= arr[left] && arr[mid]>=arr[right]){return mid;}else{return right;}}

快速排序總結：

• 對于升序排序：begin找>= key的數，end找<= key的數。

• 對于降序排序：begin找<= key的數，end找>= key的數。

• 快速排序中的begin和end是尋找左右錯位元素進行交換的關鍵。

• 最后交換基準值和begin所指的元素，完成一次劃分。

• 對于有序序列，我們需要利用一個“三數取中”規避選取最大或者最小元素作為基準值，增加復雜度和額外的棧的開辟。