【手撕排序2】快速排序

🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

🐼前言

🌟在上一节我们实现了希尔排序，感受到了插入排序的魅力，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 希尔排序，这节小编将带领大家感受交换排序的美学。

🐼快速排序

🔍 快速排序:快速排序是一种二叉树结构的交换排序，思想是:任取排序序列中的数字为基准值，按照基准值将待排序列划分为左右两个子序列，保证左序列的值均小于基准值，右序列的值均大于基准值。然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
📋 总结:找基准值，划分左子序列，划分右子序列。每一轮排序都能定位一个基准值，这样每一次递归一个基准值就在相应位置上了。

🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
快速排序主逻辑:

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort1(arr, left, right);//基准值
	QuickSort(arr, left,keyi-1);//左序列
	QuickSort(arr, keyi+1, right);//右序列
}

🌻代码解析

📋设置递归出口，如果左索引大于右索引，表示定位到所有基准值。接着，找基准值，保证左序列的值均小于基准值，右序列的值均大于基准值。keyi的位置已经排好，再递归左子树，(左序列:[left,keyi-1])再递归右子树(右序列[ keyi+1, right])。
下面我们来实现找基准值，并让这个左序列的值均小于基准值，右序列的值均大于基准值这个步骤。

🐼hoare版本

🍐在上述 PartSort1⽤于按照基准值将区间[left,right)中的元素进行划分。我们先来实现hoare版本。
在hoare版本中，初始我们让基准值keyi就是第一个元素的下标，还需要定义两个指针left,right，一个指针right从右向左找比基准值小的或相等的元素，一个指针left需要从左向右找比基准值大的或相等元素。找到了两个元素，进行交换(并让left和right分别走一步，避免死循环)，直到left>right,跳出循环。最后，让keyi处的值与右下标right的值交换。即arr[right]作为新的基准值，这样right作为基准值在该在的位置，也保证了左序列的值均小于基准值，右序列的值均大于基准值。
数组 {4,6,7,2,1,8,9,5,3 ,0}进行一轮:

hoare版本代码实现

// 快速排序hoare版本
int PartSort1(int* arr, int left, int right)
{
	int keyi = left;
	left++;//从keyi的下一个位置找
	while (left <= right)
	{
		//从右向左找比基准值小的
		while (left<=right && arr[right] > arr[keyi])
		{
			right--;
		}
		//从左向右找比基准值大的
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//找到满足的right和left
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	//将基准值与右坐标交换
	Swap(&arr[keyi], &arr[right]);
	return right;
}

👀为什么在找基准值的最后(left>right)，一定是arr[right]<=arr[keyi]？
因为在遍历的过程中，left从左向右走，一定保证了比基准值小，当right走到left左边，一定比arr[keyi]小。
👀为什么在交换过程中，不是直接交换，交换完让right,left走一步?
在我们写的hoare排序版本中，我们right从右向左找比基准值小的或相等的元素，一个指针left需要从左向右找比基准值大的或相等元素。所以对于{2,2,2,2,2}这样的序列，left和right找到完，如果不更新，会造成死循环。
👀为什么left从左向右为什么要找到大于或等于的元素，为什么不直接找到大于的元素呢?
如果一定找到比基准值大或比基准值小的元素，那么对于一组升序的数字{1,2,3,4,5…}right从右向左找比基准值小的或相等的元素，直到找到了1，基准值1与1交换。然后基准值没有左序列，只有右序列，那么每次找基准值要排序的个数都少1。所以，如果数组原本就有序，或数组元素时间复杂度过高，就为O(N^2).
👀为什么当left和right相遇了，不跳出循环?
当left和right指针相遇时，并不立即跳出循环的原因是，即使两个指针相遇，它们指向的位置的元素可能与基准值不等，需要进一步比较和交换以达到排序的目的，比如如果left和right同时指向4,基准值为2，此时让2,4交换，显然错误，所以，right需要小于left。
🍂画图剖析：
排列数组为{4,1,6,7,3}

🍀测试结果:

🐼挖坑版本

🍐挖坑版本的还是需要需要创建两个指针left和right，其思想是:我们需要先事先挖好一个坑hole,假设坑位刚开始是起始位置。保存基准值key为起始坑的位置(key = arr[hole])。
🍐现在我们需要填坑，从右向左找一个比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的基准值放入当前的"坑"中，返回当前"坑"下标（即基准值下标）。
挖坑版本代码实现:

// 快速排序挖坑法
int PartSort2(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[hole];//保存起始洞值
	while (left < right)
	{
		//从右向左找到一个比基准值小的
		while (left<right && arr[right]>key)
		{
			right--;
		}
		//该值覆盖洞值，并更新洞
		arr[hole] = arr[right];
		hole = right;
		while (left<right && arr[left]<key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	//返回基准值
	return hole;
}

🍂画图剖析：
在这里插入图片描述

🔍我们需要不断地从右向左找到比基准值小的，拿来填旧坑位，当前坑位就变成了新坑位，从左向右找到比基准值大的，拿来填旧坑位，当前坑位就变成了新坑位，最后，将最开始的基准值与当前坑位交换，当前坑位就是新基准值下标。这样从左向右找比基准值小的数据，放到前面。保证一轮循环下来。比基准值小的都在左边，比基准值大的都在右边。

🐼前后指针版本

🍐在前后指针中我们需要定义前后指针prev,cur。其思想是:让cur去前面探路，如果cur找到比基准值小的，然后prev先++,再将cur和prev所在位置交换。否则cur就一直向后找。最后，跳出循环，交换基准值和prev所在的数据。
🍐这样从左向右找比基准值小的数据，放到前面。保证一轮循环下来。比基准值小的都在左边，比基准值大的都在右边。
前后指针代码:

// 快速排序前后指针法
int PartSort3(int* arr, int left, int right)
{
	int prev = left, cur = prev + 1;
	int keyi = left;
	while (cur<=right)
	{
		if (arr[cur] < arr[keyi] && cur != ++prev)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}