完整解析快速排序

发布于：2023-01-04 ⋅ 阅读:(346) ⋅ 点赞:(0)

目录

前言

在上一篇博客中介绍了直接插入排序、希尔排序，直接选择排序以及堆排序；本篇博客则主要介绍快速排序；在先前的博客内容中的qsort在库中就是用快速排序编写的；而快速排序与冒泡排序一样都属于交换排序；
在这里插入图片描述

1.交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置；交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

简而言之，就是交换数值从而达到有序！

2.快速排序(递归)

在这里插入图片描述

从上图的结论可以看出，快速排序就是找一基准值不断进行调整从而使基准值的左边都小于它，基准值的右边都大于它；此时这个基准值就调整到它合适的位置上了。当完成一次上述过程时就排好了一个数据；重复上述过程即可完成排序！

如果需要实现上述基本思想，目前存在3种方法；

2.1hoare版本

hoare版本的基本思想是将基准值key设置在最左边，此时右边先移动，寻找比key小的值，找到后停在该位置上，将该位置记为right；接下来，左边开始寻找比key大的值，找到后停在该位置上，将该位置记为left；对left、right这两个位置进行数据交换即可；最后二者相遇，将相遇位置与key进行交换即可。图示原理如下图:
在这里插入图片描述

而完成上述一次过程后，所设定的key值得左边的数都比它小，右边的数都比它大；重复这个过程也就是上面介绍的快速排序了，而将基准值设置在左边，右边先走的目的是保证相遇位置比key小

具体步骤：

  1. 选出一个key，一般是最左边或是最右边的。
  2. 定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
  3. 在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
  4. 此时key的左边都是小于key的数，key的右边都是大于key的数
  5. 将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
int PartSort1(int* arr, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//R找比keyi位置小的数据
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		//L找比keyi位置大的数据
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		if (left < right)
			Swap(&arr[left], &arr[right]);
	}
	
	//处理相遇时的情况
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

上述代码则是一次排序的代码；而重复这些代码过程就需要进行递归了，因此有：

void QuckSortRecursion(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = PartSort3(arr, begin, end);
	QuckSortRecursion(arr, begin, mid - 1);
	QuckSortRecursion(arr, mid + 1, end);
}

在递归中，可以看到在调用时他的begin、end在每次调用时值都不同。观察上面动图，可以清楚发现，在经过一次排序后，所设定的key值就已经处于其应该存在的位置了，换句话说就是在一堆数据中key已经排好序了；所以在进行在此调用时，左边调用区间就是（begin, mid - 1），右边的调用区间是（mid + 1, end）；它的这种调用逻辑展开的话就和二叉树的逻辑一模一样，所以在经过二叉树的那些相关操作遍历后对于上述分区间排序递归调用就很容易理解了。

视频链接如下：hoare版本的快排

然而在排序中是存在这样几个问题的：

  1. L遇到R时的相遇位置是否比key小？

答案是毋庸置疑的,因为R先走，当R先停下的时候，说明R此时位置的值是比key小的，所以当L向右走直到二者相遇后，相遇位置是比key小的。

  1. R遇到L时的相遇位置是否比key小？

当L完成一次交换后，所处的位置的值就是比key小的，所以当R持续向右走直至二者相遇，此时相遇的位置一定比key要小；而当序列有序时，R一直向左走，L不动，此时交换key与相遇位置，序列相当于不变;所以这种情况也是比key要小的！

当然，关于key的取值也是可以取右边的；

int PartSort1(int* arr, int left, int right)
{
	int keyi = right;
	while (left < right)
	{
	    //L找比keyi位置大的数据
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		//R找比keyi位置小的数据
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		
		if (left < right)
			Swap(&arr[left], &arr[right]);
	}
	
	//处理相遇时的情况
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

如果key取右边的话，就需要左边先走取寻找比key大的数，右边后走去寻找比key小的数，这样做的目的是保证相遇位置比基准值大。

视频中提到递归深度是log N的，而当一组序列有序的情况下递归的深度还是log N吗？

答案是否，肯定不是的。
在这里插入图片描述
当存在有序或者接近有序的序列进行快排递归时，类似于二叉树的左边，也就是做左区间是基本直接return的，对于右区间则每次进行递归调用，如果存在N个数，每次少1个数，那么这种情况下它的递归深度是N的，此时如果数据量过大时就会形成栈溢出的，那该如何避免这种情况呢？

2.1.1三数取中法

为了解决上述数据量过大，递归深度太深从而造成栈溢出的问题。引入三数取中的方法，将有序或接近有序的序列的首元素值调整为该序列的中间值，从而就形成了二叉树形式的递归了，从而也就解决了递归深度为N造成栈溢出的问题了！

//优化keyi防止有序的情况下造成栈溢出的情况
//三数取中法
int MidSearch(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[right] > arr[mid])
		{
			return mid;
		}
		else if (arr[right] < arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}

	//arr[left]>=arr[mid]
	else
	{
		if (arr[right] < arr[mid])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

因逻辑简单，就不多介绍；但正是利用这种简单逻辑的代码从而完美的解决了递归深度过深的问题了！

三数取中的使用：

//hoare法
//keyi设置在左边，右边先进行寻找，保证相遇位置比keyi小
//keyi设置在右边，左边先进行寻找，保证相遇位置比keyi大
int PartSort1(int* arr, int left, int right)
{
	int mid = MidSearch(arr, left, right);
	Swap(&arr[mid], &arr[left]);

	int keyi = right;
	while (left < right)
	{
		//L找比keyi位置大的数据
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		//R找比keyi位置小的数据
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		
		if (left < right)
			Swap(&arr[left], &arr[right]);
	}
	
	//处理相遇时的情况
	int meeti = left;
	Swap(&arr[meeti], &arr[keyi]);
	return meeti;
}

其实，在利用三数取中的方法后就基本不会出现栈溢出的问题了，此时的函数栈帧的递归调用就会形同二叉树一般，效率大大调高了。但是，我们知道二叉树的结构是越往下数据量是越大的，保守估计可能占据到多一半的情况(在这不进行推演，有兴趣的可以自行推演)，为了解决这一问题，也就有了小区间优化的办法！

2.1.2小区间优化

小区间优化其也就是当数据量小于某一设定值之后，因为数据量不大，且接近有序所以就会使用直接插入排序进行优化！

void QuckSortRecursion(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(arr+begin, end - begin + 1);
	}
	int mid = PartSort1(arr, begin, end);
	QuckSortRecursion(arr, begin, mid - 1);
	QuckSortRecursion(arr, mid + 1, end);
}

通过小区间优化，则递归深度比log N还要少！

2.2挖坑法

思路：先设定最左边为坑位并将最左边的数值设置为key；此时右边开始走，寻找比key小的数放置到坑位中，然后更新坑位与key值，然后左边在开始走，寻找比新的key值大的数，再次更新坑位与key值即可。

在这里插入图片描述

//挖坑法
int PartSort2(int* arr, int left, int right)
{
	int mid = MidSearch(arr, left, right);
	Swap(&arr[mid], &arr[left]);

	int key = arr[left];
	int hole = left;
	while (left<right)
	{
		//R找小，将找到的较小值放到坑位中
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		//L找大，将找到的较大值放到坑位中
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	//相遇
	arr[hole] = key;
	return hole;
}

在经过hoare的摧残后，挖坑法就显得比较简单了。通过右边寻找比坑位小的值，找到后进行坑位与key的更新；更新完成后，在通过左边寻找比坑位大的值，找到后再次进行坑位与key的更新即可！

2.3前后指针法

前后指针法相比于上面两种办法就显得更加简单了。设置两个变量prev、cur,当cur碰到比基准值小的，首先prev++,然后cur与prev进行交换即可。详细思路见下图：
在这里插入图片描述

//前后指针法
//cur寻找比keyi位置小的数据与prev进行交换
int PartSort3(int* arr, int left, int right)
{
	int mid = MidSearch(arr, left, right);
	Swap(&arr[mid], &arr[left]);
	//
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] <= arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	Swap(&arr[prev], &arr[keyi]);

	return prev;
}

当prev++后如果与cur的位置重合后，此时的交换是没有意义的，所以针对这种情况if判断中就添加了限制条件。当cur位置比key小的话，并且prev和cur位置不重合，此时进行交换即可！最后cur会越界从而跳出while循环，此时因为prev与cur的交换从而使prev的位置存储着比key小的值，所以最后prev与keyi位置数据进行交换即可满足基准值的左边比它小，右边比它大。

3.快速排序(非递归)

上述的快速排序时利用递归实现的，同样也可以使用非递归去实现快排；然而非递归去实现快排需要借助数据结构中的栈：没错，我是栈

在利用栈实现快速排序时其实也就是在模拟递归的过程，直接上代码：

//快速排序(非递归实现)
void QuckSortNRecursion(int* arr, int begin, int end)
{
	Stack st;
	InitStack(&st);
	PushStack(&st, begin);
	PushStack(&st, end);
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		PopStack(&st);
		//
		int left = StackTop(&st);
		PopStack(&st);
		//
		int keyi = PartSort3(arr, left, right);
		
		
		//重新放入区间
		if (right > keyi + 1)
		{
			PushStack(&st, keyi + 1);
			PushStack(&st, right);
		}
		
		if (keyi - 1 > left)
		{
			PushStack(&st, left);
			PushStack(&st, keyi - 1);
		}
	}
	StackDestory(&st);
}

首先进入while循环前先将大区间压入到栈中，进入后，对区间进行保存然后弹栈；注意栈是先入后出，所以先接收right，后接收left。然后进行排序。排序完成后利用返回的keyi进行区间的划分，对于只有begin和end重合的以及begin>end的这两种情况不进行压栈。否则将其区间进行压入。压栈的时候为了保持与递归的逻辑一致，所以先压栈右部分区间。在压栈左部分区间，根据这个原理就可以先完成左区间的排序了。

具体的过程是需要自己手动进行调试的。函数接口直接可以拿过去用，设置main函数调用接口传参就可以调试了！

Ending

关于快排就介绍完成了，而快排和冒泡都是属于交换排序的，因为冒泡几乎是最简单的排序了，所以就没有写出来；快排的三种实现还是比较难以理解的，所以需要多调试几遍，递归不清楚的可以转到二叉树哪里，里面有我录制的递归调用的视频可以进行参考！

OK，就这样吧🙋‍♂️
在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布