目录

1.挖坑法

执行流程

代码

运行结果

可读性好的代码

2.前后指针法(双指针法)

执行流程

单趟排序代码

将单趟排序代码改造后

写法1

简洁的写法

3.思考题

---

1.挖坑法

执行流程

"挖坑法"顾名思义:要有坑位,一开始将关键值放入临时变量key中,在数组中形成一个坑位

左边做key,右边先走,先right找到小,将小值放入坑位中,坑位被转移

left找到大,将大值放入坑位中,坑位被转移 

重复上述过程

最终left和right相遇,在坑位填上key的值,单趟快速排序结束,之后对左右两个区间排序,递归处理,写成完整的挖坑法的快速排序

注意:对比120.【C语言】数据结构之快速排序(详解Hoare排序算法)文章写的Hoare快速排序,本方法无需交换函数

代码

void QuickSort_Hole(int* arr, int left, int right)//挖坑法(对着Hoare排序修改即可
{if (left > right)return;int begin = left;int end = right;int key = arr[left];//对比Hoare排序,不需要key的下标key_i,且不能保存下标,否则值覆盖会丢失数据while (left < right){//由于key_i==left,因此right指针先走//右边找小while (left < right && arr[right] >= key){right--;}arr[left] = arr[right];//填坑位//左边找大while (left < right && arr[left] <=key){left++;}arr[right] = arr[left];//填坑位}arr[left] = key;//此时left==rightQuickSort_Hoare(arr, begin,  left- 1);QuickSort_Hoare(arr, left + 1, end);
}

main.c写入以下代码

#include "Sort.h"
int main()
{int arr[] = { 6,1,2,7,9,3,4,5,10,8 };printf("排序前:");PrintArray(arr, sizeof(arr) / sizeof(arr[0]));QuickSort_Hole(arr, 0,sizeof(arr) / sizeof(arr[0])-1);printf("排序后:");PrintArray(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

运行结果

虽然能完成快速排序,但该代码的可读性较差,建议专门定义一个变量hole_i表示坑位的下标,则arr[hole_i]表示坑位,可写成如下形式

可读性好的代码

//可读性好,有hole_i变量
void QuickSort_Hole(int* arr, int left, int right)//挖坑法(对着Hoare排序修改即可
{if (left > right)return;int begin = left;int end = right;int key = arr[left];//对比Hoare排序,不需要key的下标key_i,且不能保存下标,否则值覆盖会丢失数据int hole_i = left;//记录坑的下标while (left < right){//由于key_i==left,因此right指针先走//右边找小while (left < right && arr[right] >= key){right--;}arr[hole_i] = arr[right];//填补坑位hole_i = right;//修改坑位下标//左边找大while (left < right && arr[left] <= key){left++;}arr[hole_i] = arr[left];//填补坑位hole_i = left;//修改坑位下标}arr[hole_i] = key;//此时left==rightQuickSort_Hoare(arr, begin, hole_i - 1);QuickSort_Hoare(arr, hole_i + 1, end);
}

2.前后指针法(双指针法)

执行流程

设前指针prev和后指针cur

设排升序,单趟快排流程

1.最开始prev指向arr[0],cur指向arr[1]

2.cur找到比key(key==arr[key_i])小的值,prev++,arr[cur]和arr[prev]位置的值交换,cur++

3.cur找到比key大的值,cur++

4.重复1和2,直到cur遇到数组的边界时,让arr[key_i]和arr[prev]互换,单趟快排结束

设key_i==0,则arr[key_i]==6,数组长度为n,对[0,n]这一闭区间排序

 

 

 

 

 

 

 

 

 

从图中可以看出两点

1.prev要么紧跟着cur(prev+1==cur);要么和cur中间间隔比key大的一段区间;

2.把比key大的值往右翻,比key小的值,翻到左边

 arr[prev]的左边比6小,右边比6大,之后对绿色和蓝色区域再快速排序

单趟排序代码

int prev = 0;int cur = 1;int key_i = 0;while (cur < n){if (arr[cur] > arr[key_i]){cur++;}else{prev++;if (cur != prev)//避免自己和自己交换,无意义{Swap(&arr[cur], &arr[prev]);}cur++;}}Swap(&arr[key_i], &arr[prev]);

将单趟排序代码改造后

写法1

void QuickSort_Prev_And_Cur_Pointer(int* arr,int left,int right)
{if (left >= right){return;}int prev = left;int cur = prev+1;int key_i = left;while (cur <= right)//由于是闭区间,因此cur<=right!!cur可以取等{if (arr[cur] > arr[key_i]){cur++;}else{prev++;if (cur != prev)//避免自己和自己交换,无意义{Swap(&arr[cur], &arr[prev]);}cur++;}}Swap(&arr[key_i], &arr[prev]);QuickSort_Prev_And_Cur_Pointer(arr, left, prev - 1);QuickSort_Prev_And_Cur_Pointer(arr, prev + 1, right);
}

QuickSort_Prev_And_Cur_Pointer(arr, 0,sizeof(arr) / sizeof(arr[0])-1);//一定有-1

一定要注意while (cur <= right)一定要取等!!

简洁的写法

	while (cur <= right)//由于是闭区间,因此cur<=right!!cur可以取等{if (arr[cur] < arr[key_i] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}

---

上述提到的这两种方法仍然需要递归,过多数会导致栈溢出,下篇文章会讲解决方法

3.思考题

key在右边时(即arr[key_i]==arr[right]),前后指针法怎么写?