🍃 如果觉得本系列文章内容还不错,欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍
目录
- 🐼前言
- 🐼快速排序
- 🐼hoare版本
- 🐼挖坑版本
- 🐼前后指针版本
- 🐼文末
🐼前言
🌟在上一节我们实现了希尔排序,感受到了插入排序的魅力,如果感兴趣的小伙伴,可以阅读我的上一篇文章:> 希尔排序,这节小编将带领大家感受交换排序的美学。
🐼快速排序
🔍 快速排序:快速排序是一种二叉树结构的交换排序,思想是:任取排序序列中的数字为基准值,按照基准值将待排序列划分为左右两个子序列,保证左序列的值均小于基准值,右序列的值均大于基准值。然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
📋 总结:找基准值,划分左子序列,划分右子序列。每一轮排序都能定位一个基准值,这样每一次递归一个基准值就在相应位置上了。
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
快速排序主逻辑:
//快速排序
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和leftif (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;
}
🍂画图剖析:
👀为什么限制条件要加上cur != ++prev
因为当prev先走向下一个位置,此时刚好和cur重合,此时交换是无意义的,应该让cur继续移动。
👀为什么要先让prev++,再与cur交换
因为prev所在位置是已经调整好的数据,所以要先让prev先移动到下一个位置。
🐼文末
感谢你看到这里,如果觉得本篇文章对你有帮助,点个赞👍 吧,你的点赞就是我更新的最大动力 ⛅️🌈 ☀️