1.什么是快速排序
我们知道排序有很多种,常见的如希尔排序,插入排序,选择排序,堆排序等等,而快速排序也是排序家族中的一员。因为其在大多数情况下有着优秀的综合性能,快速排序的快速也算是实至名归,接下来就为大家讲解快速排序的思想与实现。
2.快速排序的核心思想
快速排序通过多次比较与交换来完成排序。而这个过程又被分为了多次重复单趟排序,接下来我们先从每一趟的排序讲起。
快速排序的单趟排序思想是:
在一个无序数组中取一个数key,每一趟排序的最终目的是:让key的左边的所有数小于key,key的右边都大于key(假设排升序)。
先不考虑这一步怎么实现,我们接着往下看。
以下面的数组为例,可以观察到的是,在完成单趟排序后,无论key的左边和右边是否有序,key都来到了它在整个数组有序时应该来到的位置,也就是这个数组的第四个位置。所以对于key来说,它已经被排好序了。
接下来,我们对key的左右区间进行单趟排序,可以预见的是,每次排序都固定好了一个数。而当我们对细分的左右区间进行单趟排序,最终整个数组都会化为有序。
下面是快速排序的整体框架:
void QuickSort(int* a, int left, int right)
{
if (left >= right)//如果区间只剩一个数或没有数就不进行操作
return;
int key = PartSort(a, left, right);//调用单趟排序函数,取key的位置
QuickSort(a, left, key - 1);//递归调用,对左区间进行排序
QuickSort(a, key + 1, right);//递归调用,对右区间进行排序
}
3.单趟排序三种方法
1.hoare方法
这个方法取自于快排的发明者本人
其单趟排序的思路是:取区间中最左或最右边的元素为key,定义两个变量,这里假设是p和q,q从区间的最右边向左走,找到比key小的元素就停下。p从最左边向右走,找到比key大的元素就停下。然后交换p和q所指向的元素。下面是p与q单次交换的示意图:
重复上面的过程,直到pq相遇,交换key和pq相遇位置的元素。
这样,单趟排序就完成了。
可以看出,经过pq的不断交换,比key小的值换到了左边,比key大的值换到了右边。最终将key换至中间就完成了单趟排序。
这里的key可以取最左边的值,此时必须让最右边的q先走。因为在最后一个循环时,若是q向左走,撞上了p,p此时指向的元素是上一个循环结束后交换的值,这个值比key小。若是p向右走,撞上了q,那么在这个循环,q先走,并且q停下来了,所以q的位置是一个比key小的值。若让左边的p先走,则可能在最后交换key的步骤将一个大于key的值交换到最左边。具体原因不进行分析。
若药取最右边的值做key,则要让最左边的p先走,原因同上。
下面是代码实现:
int PartSort1(int* a, int left, int right)
{
int key = left;//取最左边的元素做key
while (left < right)//当左右没有相遇
{
while (left < right && a[right] >= a[key])//如果右比key小就退出循环
right--;
while (left < right && a[left] <= a[key])//如果左比key大就退出循环
left++;
swap(&a[left], &a[right]);//交换左右
}
swap(&a[key], &a[left]);//交换key和相遇位置的元素
return left;//返回key的位置
}
2.挖坑法
这个方法单趟排序的思路是:取最左或最右边的元素为key,假设把这个位置“挖空”,让最右边的q向左走,直到遇到比key小的数,将其放到key的位置,自己的位置变“空”。直到pq相遇,那么这个位置就是最终的坑位,再将key填入这个坑位,就完成了一趟排序。
单趟交换示意图:
代码实现:
int PartSort2(int* a, int left, int right)
{
int key = left;//取最左边的元素做key
int x = a[left];//用变量x保存key的值
while (left < right)
{
while (left < right && a[right] >= x)//从右往左找,找到比key小的值就停下来
right--;
a[key] = a[right];//将元素填入坑内
key = right;//更新坑的位置
while (left < right && a[left] <= x)//从左往右找,找到比key大的值就停下来
left++;
a[key] = a[left];//将元素填入坑内
key = left;//更新坑的位置
}
a[key] = x;//最后将key的值填到坑内
return key;//返回key的位置
}
3.快慢指针法
取最左边的数为key,定义两个快慢指针,都从key的下一位往右走,fast每走一步判断一下它指向的元素是否小于key,若小于则交换fast和slow位置的元素,并且让slow向前走,直到fast走到底,结束循环。最后让slow和key位置的值交换。再返回key的位置。
代码实现:
int PartSort3(int* a, int left, int right)
{
int key = left;//取最左边的值为key
int fast = key + 1;//定义快指针(实际是下标)
int slow = key;//定义慢指针(实际是下标)
while (fast <= right)
{
if (a[fast] < a[key])//当快指针指向元素小于key就交换
{
swap(&a[fast], &a[++slow]);//交换元素并且慢指针向前走
}
fast++;//快指针向前走
}
swap(&a[key], &a[slow]);//慢指针回退一位再交换
return slow;//返回key的位置
}
注意这里的slow初始位置和fast不同,因为交换元素时要使用前置++,若使用后置++则要改写为下面的写法。因为如果每次交换都采用后置++,最终slow的位置会在期望位置的下一位,所以与key交换时要回退一位。而上面的更简洁,故采用上面的写法。
int PartSort3(int* a, int left, int right)
{
int key = left;
int fast = key + 1;
int slow = key + 1;//起始位置不同
while (fast <= right)
{
if (a[fast] < a[key])
{
swap(&a[fast], &a[slow++]);//采用后置++
}
fast++;
}
swap(&a[key], &a[--slow]);//需要回退一位
return slow;
}
4.非递归实现快速排序
我们知道快速排序的思路就是将区间用key划分为左右两个小区间,再进行递归。
要用非递归的方式实现快速排序,我们可以借助栈来完成。
对于一个区间,我们可以化为栈中的两个元素进行表示:
比如表示[0,4]区间,我们可以先入0再入4。在取出时,我们先取到4,再取到0,这样就算是取出区间了(要注意出栈顺序与入栈顺序相反)。
具体的实现思路是:
先将整个区间入栈,然后进入循环体:取出区间,进行一趟快速排序,得到左右区间,再将左右区间入栈。直到整个栈为空就退出循环。
这样在每次循环中,就取出了要排序的区间,再将左右区间入栈,在之后的循环中排序,直到所有区间都被拆分排序到不可再拆分。
代码实现:
void QuickSortNonR(int* a, int left, int right)
{
stack<int> st;//建立栈
st.push(left);//将区间入栈
st.push(right);
while (!st.empty())//当栈不为空进入循环
{
right = st.top();//取区间最右值
st.pop();//出栈
left = st.top();//取区间最左值
st.pop();//出栈
int key = PartSort3(a, left, right);//对区间进行一趟排序,取得key值
if (left < key - 1)//如果左区间可以再分,就入栈
{
st.push(left);
st.push(key - 1);
}
if (key + 1 < right)//如果右区间可以再分,就入栈
{
st.push(key + 1);
st.push(right);
}
}
}
5.两种优化快速排序的思想
1.三数取中
面对完全有序的数组,快速排序每趟排序后,key的位置都在边缘,每层递归都只能固定一个数,时间复杂度变成了O(N^2)。
面对这种情况,我们可以在取key时动手脚。每次取key我们不再只取最左或最右的值。而是对比最左、最右、中间的三个元素,取三个元素中,值在另外两者中间的元素作为key。这样,就打乱了有序数组,大大加快了快速排序在面对这种情况时的速度。
2.小区间优化
快速排序对一个元素不多的数组排序,仍需要进行多次递归调用,我们知道递归是比较消耗资源的,所以为了避免在快速排序递归的最后几层大量调用函数,我们可以在数组元素较少时不再递归,而是采用选择排序替代,这样就能在不损失多少速度的情况下减少大量的递归次数,达到优化速度的目的。
今天的文章快速排序详解分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/8292.html