快排还能变出花儿？——浅析快排算法的2种写法(尤其考研党要特别注
在数据结构和算法的学习中，一种经典的算法——快速排序算法(简称快排)，由于其优秀的性能，在解决实际问题中有着特别出色的性能，同时也是计算机考研中数据结构这门课的必考算法之一。
快排的思想是一致的，但是快排的细节却可能有很多的不一样。这使得——单次排序后的结果很有可能不同。尤其在考研党中，因为考试要求写出快排的具体过程，很有可能因此得出错误的答案。
接下来我们就来看看两种快排，在结果上会有哪些不同
快排简介
大家先来了解一下快排，下面这段引自维基百科:
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nlog n)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nlogn)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
其次，快排使用的是分治的思想，用大白话来解释就是：
分治就是把一个大问题，转化为一个小问题，然后再分别对各个小问题进行分解，分解到一定很小的规模的时候，得出答案，再按照原路径一层一层的返回结果、合并结果，因此分治常常与递归结合使用。
快排的是怎么运行的
给定一个无序序列，目的是将其变成有序的。
步骤1.选定一个基准数，
步骤2.将剩余的数排成两堆
小于基准数的为一堆，大于的另一堆，两堆数内部顺序不重要。怎么分成2堆，正是此次讨论的差异所在
步骤3.将这个基准数放入中间
此时这个数的位置是排序后的绝对位置，因为左边的数都比它小，右边的数都比它大，而在有序序列中，每一个数都满足左边的比它小，右边的比它大。
步骤4.对左边那堆数执行1-3步，对右边那堆数执行1-3步
步骤5.(终止条件)一堆数中只有1个数
举个例子🌰，有一序列：
int nums[]={49,38,65,97,76,13,27};
首先选定 49 作为基准数，
比它小的数有: 38 13 27（暂时不管顺序）
比它大的数有: 65 97 76（暂时不管顺序）
所以（3个数）49 （3个数）
49已经被安排到最终的位置，其他排序则可以不用动49的位置，以此往复循环。
可以写出以下的代码：
int QuickSort(int iDatas[],int iLeft,int iRight)
{
if(iLeft<iRight){
int loc=partition1(iDatas,iLeft,iRight); //确定中间数
//int loc=partition2(iDatas,iLeft,iRight); //另外一种方法
QuickSort1(iDatas,iLeft,loc); //排左边数
QuickSort1(iDatas,mid+1,iRight); //排右边数
}
return 0;
}
其中partition函数会把传入的iDatas序列中的第一个数作为基准数，并把两边的
的代码分到这个基准数的两边，函数返回的是基准数最后所处的位置，我们可以通过这个返回的位置，来确定剩余的需要排序的两堆数的下标。
而partition函数怎么正是本文所述的“两种”方法的差异所在。
两种排序方法
剩下的工作，就聚焦在partition函数是怎么编写的了
有2种办法：
方法1:
1、固定第一个数为基准数
2、两个下标i和j，分别从基准数的下一个，和最后一个开始往中间出发
3、分别找到一个在左边大于基准数的a和右边小于基数的b
4、交换a和b
5、重复2-4直到分成两堆
6、交换基准数和左边一堆数中(比基准数小的数)靠右的数
方法2:
1、两个下标i和j，分别从基准数和最后一个出发
2、找到比基准数的小的数，交换基准数和这个数
3、从左边出发找到比基准数大的数，交换基准数和这个数
4、重复2-3
不难发现，该方法中每次交换都有基准数的参与，不停地交换基准数和与基准数比较后但位置不对但数。为了节约该方法中频繁交换的基准数，我们可以先使用一个临时变量保存基准数的数值，而其中的交换操作直接更改为覆盖基准数所在的位置，最后才把基准数放到对应的位置。该方法也是严蔚敏教材中的方法。
- 固定基准数，两个下标从两边开始游走( 1到size-1 )，分别找到一个在左边大于基准数的a和右边小于基数的b，交换a和b，然后继续寻找。最后交换基准数和左边一堆中靠右的数
- 两个下标分别从两边开始游走( 0到size-1 )，一个+一个-，与基准数比较大小，大的往右边放，小的往左边放(“放”通过交换来实现)
话不多说，直接贴代码
方法1:
int partition1(int iDatas[],int iLeft,int iRight){ //固定左边的数
int i=iLeft+1,j=iRight;
int temp=iDatas[iLeft]; //基准数
while(i<=j){
while((iDatas[i]<=temp)&&(i<=iRight)) i++;
while(iDatas[j]>temp) j--;
if(i<j){
std::swap(iDatas[i],iDatas[j]); //交换
i++;j--;
}
}
std::swap(iDatas[iLeft],iDatas[j]); //交换基准数和左边一堆中靠右的数
return j;
}
方法2:
int partition2(int iDatas[],int iLeft,int iRight){
int temp=iDatas[iLeft]; //保存基准数
int i=iLeft,j=iRight;
while(i<j){
while(iDatas[j]>=temp && i<j) j--;
iDatas[i]=iDatas[j]; //直接覆盖，不交换
while(iDatas[i]<=temp && i<j) i++;
iDatas[j]=iDatas[i]; //直接覆盖，不交换
}
iDatas[i]=temp; //最后把基准数放入对应的位置
return i;
}
对比两种方法一趟排序后的顺序
int main()
{
const int size=7;
int nums1[size]={49,38,65,97,76,13,27};
int nums2[size]={49,38,65,97,76,13,27};
partition1(nums1,0,size-1);
partition2(nums2,0,size-1);
myPrint(nums1,size);
myPrint(nums2,size);
}
其中myPrint为:
int myPrint(int iDatas[],int size)
{
for(int i=0;i<size;i++)
std::cout<<iDatas[i]<<" ";
std::cout<<std::endl;
return 0;
}
运行后输出为
13 38 27 49 76 97 65
27 38 13 49 76 97 65
我们可以看到，49已经处于序列中的绝对位置，其左边的数字都比它小，右边的数字都比它大
但是，49左边3个数的顺序是不一样的，这正是因为两种方法在分堆的过程中，排序的顺序不一样。
而在计算机考研-数据结构的考试中，常常要求写具体的步骤，这两种情况下，就会造成与答案不一致。
在此，建议各位仔细查看学校考试指定书籍里的快排使用的是哪种方法，按照教材的来。若无指定书，也无明确说明，建议写第二种，也就是严蔚敏教材中所推荐的方式。
其他不考研的读者，看着乐乐就好，拓宽一下思路，尤其是面试的时候如果面试官问到快排，可以多给点思路，弄得面试官一愣一愣的，offer自然就到手了(开个玩笑， 大家还是好好认真打好基础)
最终排序
虽然其一躺排序完成后顺序可能是不同的，但是最后排序完成都是正确的升序。
QuickSort(nums,0,size-1); //全部排序完成
查看结果
13 27 38 49 65 76 97
感谢你的阅读，我们下篇博客，再见！
作者info
个人主页：https://me.csdn.net/m0_46415159
本文链接：https://blog.csdn.net/m0_46415159/article/details/104805950
