递归实现快速排序的三种方法

快速排序的定义

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

个人一些见解

什么是递归？为什么递归可以实现快速排序？

很多人对于递归的认识只是局限于对函数的再次调用（比如说画函数递归图）

比如二叉树的先序遍历,但其实我们换一个角度想，为什么递归可以实现深度优先遍历的过程？

显然，递归可以实现快速排序也是满足于这种结构。

过程1：以某个元素为基准将数组划分为三部分，基准值左边小于它，右边大于它，这一步就完成了基准值位置的确定

过程2：将基准值左边的过程进行排序（会发现该过程也需要经历123）

过程2：将基准值右边的过程进行排序（会发现该过程同样需要经历123）

所以主函数的过程如下：

void QuickSort(int* arr, int left, int right)//快速排序主函数体
{
	if (left >= right)
		return;
    int div = PartSort(arr, left, right);//partsort函数是过程1的部分，下文会介绍三种方法
	QuickSort(arr, left, div - 1);//过程2
	QuickSort(arr, div + 1, right);//过程3
}

注：这里的left是要排序的左下标，right为右下标

需要注意的是：我们递归的结束条件

如果left>=right,则退出递归过程

接下来为你们讲诉一下快速排序完成过程1的三种方法

1.Hoare版本（左右指针）

我们可以设right下标对应的元素为key值，也就是基准值，实现代码如下

int Getmidindex(int* arr, int left, int right)//三个数找中间值
{
	int mid = (left + right) / 2;
	if (arr[left] > arr[mid])
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return left;
		else
			return right;
	}
	else
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] > arr[right])
			return left;
		else
			return right;
	}
}
int PartSort1(int* arr, int left, int right)//快速排序之前后指针法,返回值为key的下标
{
	int mid = Getmidindex(arr, left, right);//该函数为三数其中，确保我们不会取最值
	swap(&arr[mid], &arr[right]);
	int keyindex = right;//右下标为基准值的下标
	while (left < right)
	{
		while (left < right && arr[left] <= arr[keyindex])//从左边找到大于基准值的元素
			left++;
		while (left < right && arr[right] >= arr[keyindex])//从右边找到小于基准值的元素
			right--;
		swap(&arr[left], &arr[right]);//将两个数交换
	}
	swap(&arr[left], &arr[keyindex]);//最后将基准值放在它的位置上
	return left;//返回基准值的下标，便于主函数体进行过程2  3
}

上述代码经常存在疑惑的点

为什么右边作为基准值要从左边出发?

其实这里是为了保证当left==right时，该位置对应的值是大于或者等于基准值的。

为什么基准值不能取最值？

2.挖坑法

int PartSort2(int* arr, int left, int right)//快速排序之挖坑法,返回值为key的下标
{
	int mid = Getmidindex(arr, left, right);
	swap(&arr[mid], &arr[right]);
	int key = arr[right];//将基准值保存，基准值的位置就行出一个坑
	while (left < right)
	{
		while (left < right && arr[left] <= key)//同理找大于基准值
			left++;
		arr[right] = arr[left];//把大于基准值的值填在坑中
		while (left < right && arr[right] >= key)
			right--;
		arr[left] = arr[right];
	}
	arr[left] = key;//最后的坑就是基准值的位置
	return left;
}

为了方便理解，我将于图解的形式讲解

动态过程如上图

3.前后指针

个人认为最好理解的方法

int PartSort3(int* arr, int left, int right)//快速排序之前后指针法,返回值为key的下标
{
	int mid = Getmidindex(arr, left, right);
	swap(&arr[mid], &arr[right]);
	int key = arr[right];
	int cur = 0;
	int prev = cur - 1;//其实就是从0到prev所有下标对应的值都小于基准值，所有一开始我们初始化不能为0
	while (cur <= right)
	{
		if (arr[cur] < key)//找到一个比基准值小的值就++prev
			swap(&arr[++prev], &arr[cur]);
		cur++;
	}
	swap(&arr[++prev], &arr[right]);
	return prev;
}

总结

以上就是用递归来实现快排的三种方式，下一篇文章我们将讲解非递归来实现快排。

觉得还不错就点个小小的赞吧