数据结构自学Day13 -- 快速排序--“分而治之”
🔶 一、快速排序（Quick Sort）
📌 基本思想：
分而治之：
每次从数组中选一个“基准”（pivot），把比它小的放左边，大的放右边。
-
对左右子数组递归排序。
🧠 排序过程：
-
选择一个基准（如第一个或最后一个元素）。
-
使用双指针或 Lomuto/Hoare 分区法将数组分为左右两部分。
-
对左右子数组递归调用快速排序。
⏱️ 时间复杂度：
情况
时间复杂度
最好情况
O(n log n)
平均情况
O(n log n)
最坏情况
O(n²)（当数组几乎有序或元素都相同时）
♻️ 稳定性：
不稳定排序
✅ 优点：
-
速度快：在大多数实际情况下性能极佳。
-
原地排序：不需要额外内存。
-
几乎是排序算法中的性能王者（除非你特别追求稳定性）。
❌ 缺点：
-
最坏情况下可能退化为 O(n²)。当我们选择的基准为最大元素或者最小元素
-
递归层数深时可能栈溢出（需优化）。
-
算法思维：
-
选择基准值，利用双指针遍历数组，将比基准值小的放置左边，比基准值大的放置右边。
-
思维导图：
代码实现：
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 = 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[right]){ return left; } else if(arr[mid]>= arr[left] && arr[mid]<=arr[right] || arr[mid]=arr[right]){ return mid; } else{ return right; }}
快速排序总结：
-
对于升序排序：begin找>= key的数，end找<= key的数。
-
对于降序排序：begin找= key的数。
-
快速排序中的begin和end是寻找左右错位元素进行交换的关键。
-
最后交换基准值和begin所指的元素，完成一次划分。
-
对于有序序列，我们需要利用一个“三数取中”规避选取最大或者最小元素作为基准值，增加复杂度和额外的栈的开辟。
