数据结构自学Day13 -- 快速排序--“挖坑法”
🧠 快速排序的核心思想
快速排序的思想仍然是“分而治之”，但是这里我们介绍一种比较更容易理解的思路“挖坑法”。其核心思想仍然是“分而治之”，参考往期内容：快速排序--“分而治之”
快速排序通过分治方式实现排序：
-
从数组中选择一个元素作为基准值（pivot）；
-
将数组划分为两部分：左边的都比它小，右边的都比它大；
-
对两边递归进行排序。
🕳️ 挖坑法（Digging Hole Method）
✅ 基本流程
-
选择一个元素作为基准值，一般选 数组的最左侧 或 最右侧元素；
-
把这个值“挖出来”，形成一个坑；
-
从右向左找一个比基准小的，填到左边的坑里；
-
然后从左向右找一个比基准大的，填到右边的坑；
-
重复“找数 → 填坑 → 留坑”的过程，直到左右指针相遇；
-
把基准值填回最后一个坑中。
最终，基准值归位，左边比它小，右边比它大。
🤔思维导图：
代码实现：
//三数取中优化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; }}//挖坑法的实现int PartSort2(int* arr,int left,int right){ assert(arr); int mid_index = get_midindex(arr,left,right); Swap(&arr[mid_index],&arr[right]); int key = arr[right]; int begin = left; int end = right; while (begin< end) { //取右边值作为key，让begin先走 while(begin < end && arr[begin] <= key){ begin++; } arr[end] = arr[begin]; //取右边值作为key，end后移动 while(begin = key){ end--; } arr[begin]= arr[end]; } arr[begin] = key; return begin;}
✅ 挖坑法特点
特性
描述
实现方式
覆盖赋值填坑，不用交换函数
空间复杂度
原地排序，O(1)
时间复杂度
最好 O(n log n)，最坏 O(n²)（依赖 pivot 选择）
适用场景
大部分情况性能优秀，适合通用排序
优化策略
三数取中减少最坏情况，提升整体效率
