数据结构自学Day13 -- 快速排序--“挖坑法”

🧠 快速排序的核心思想

        快速排序的思想仍然是“分而治之”，但是这里我们介绍一种比较更容易理解的思路“挖坑法”。其核心思想仍然是“分而治之”，参考往期内容：快速排序--“分而治之”

快速排序通过分治方式实现排序：

1. 从数组中选择一个元素作为基准值（pivot）；

2. 将数组划分为两部分：左边的都比它小，右边的都比它大；

3. 对两边递归进行排序。

🕳️ 挖坑法（Digging Hole Method）

✅ 基本流程

1. 选择一个元素作为基准值，一般选 数组的最左侧 或 最右侧元素；

2. 把这个值“挖出来”，形成一个坑；

3. 从右向左找一个比基准小的，填到左边的坑里；

4. 然后从左向右找一个比基准大的，填到右边的坑；

5. 重复“找数 → 填坑 → 留坑”的过程，直到左右指针相遇；

6. 把基准值填回最后一个坑中。

最终，基准值归位，左边比它小，右边比它大。

🤔思维导图：

代码实现：

//三数取中优化
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;}}
//挖坑法的实现
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 < end && arr[end] >= key){end--;}arr[begin]= arr[end];}arr[begin] = key;return begin;
}

✅ 挖坑法特点