坚持看完，结尾有思维导图总结
什么是快排？
首先按照官方定义:
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
按照官方的定义我们看不出来什么
但是如果我们用图示的方式演示一下就能够明白
假设有一个序列 :
572136，通过单趟排序，每个数组的第一个能够找到对应的位置，同时保证这个数的左边都是比他小的数，右边都是比他大的数
排序后 ，5 的左边都是比5小的数，5的右边都是比5大的数
然后以五位分界线，将数组分为左数组和右数组，执行相同的排序
黑色的是分段
红色的是分段后回到原数组
如何实现递归
递归有两个要素，得到最后数据的位置
按照最后数据的位置切分数组
void QuickSort(int* a ,int begin,int end)
{
if(end - begin +1 <= 1)//只有一个元素的时候退出
return;
int k = PartSort(a,begin,end);
QuickSort(a,begin,k-1);
QuickSort(a,k+1,end);
}
单次的排序要如何实现
一共有三种方式实现
hore 的办法
有一个要验证的问题，如何保证最后相遇的地方保证比数据小呢？
一共有两种相遇方式，要么是 begin 遇到 end ，要么是end 遇到degin
当 begin 遇到 end 的时候，end 本身是比 key 小的值，所以保证了 遇到的数字比 key 小
当 end 遇到begin ，因为保证了 end 先走，end 行动前， begin 和 end 已经互换，begin 底下就是比 key 小的数，也能保障 相遇的值比 key 小
具体程序
void swap(int*a ,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//因为要得到最后的 key的位置，所以要返回 int
int PartSort1(int*a,int begin,int end)
{
int key = begin;
// 因为尽量不改变 begin 和 end;所以用left 和 right 代替，虽然在函数中也是临时变量
int left = begin;
int right = end;
while(left < right)
{
// right 找到比key 小的值
while(right>left && a[right]>=a[key])
{
right--;
}
// left 找到比 key 大的值
while(left<right && a[left]<=a[key])
{
left ++ ;
}
swap(&a[left],&a[right]);
}
swap(&a[key],&a[right]);
return right;
}
程序需要注意的地方
首先要满足 right 总是再后面 left 总是再前面
这样写行不行?
while(right>left && a[right]>a[key])
while(left < right && a[left] < a[key])
再这种情况下， left 和right 始终不会向前走，导致死循环
如果是
while(right>end && a[right]>=a[key])
while(left <begin && a[left] <= a[key])
会导致left 和 right 直接错过
坑位法
这是局部排序的第二个方法
图解:
int PartSort2(int* a,int begin,int end)
{
int left = begin;
int right = end;
int pit = begin;//坑位
int key = a[left];
while(left < right)
{
//right 找小
while(right>left && a[right]>=key)
{
right -- ;
}
// 把小的移动到坑位
a[pit] = a[right];
pit = right;
//left 找大
while(left<right && a[left]<=key)
{
left ++ ;
}
//把大的移动到坑位
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}
这种方法是双指针方法的拆解方式，引入了坑位，从而代替了两个指针的转换
双指针法
这种方式是最难理解，同时也是最简单的方式
之前的两种都是通过转换的方式，来把小的和大的放到对应的位置
这种方式是一种推动的方式来把小的放在数组前，大的放在数组后
int PartSort3(int*a,int begin,int end)
{
int key = begin;
int prev =begin, cur = begin;
while(cur <= end)
{
cur ++;
//相等直接跳过
if(cur<=end && a[cur] < a[key])
{
prev ++;
swap(&a[prev],&a[cur]);
}
}
swap(a+key,a+prev);
return prev;
}
为什么相等应该直接跳过，如果相等不去跳过，如果是这样的数组
5,1,5,5,5
所以在相等的时候不应该互换
总结
希望大家看完，能够有所收获
如果有错误，请指出我一定虚心改正
动动小手点赞
鼓励我输出更加优质的内容
转载：https://blog.csdn.net/carry_carial/article/details/128415519