目录

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==right
	QuickSort_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==right

	QuickSort_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]),前后指针法怎么写?