各类排序方法 手撕快排 回顾经典快排 优化版快排

快排的主要思想是分而治之

第一步，确定分界点，a

第二步，调整区间，利用分界点a，把小于分界点a的数放在左边，大于的放在右边，相等的放在哪都可以

第三步，递归处理左右两段

实现(暴力方法）

总数组是q[],然后定义两端数组，l[],r[]

找到一个分界点a

遍历q[],如果q[i]<=a,则放在l[],否则放在r[]

然后再把l[]和r[]放入q[]

实现（优美）

双指针

在区间q[]的左右两端分别放指针i,j

然后还是要确定分界点a

i和j分别往中间移动

当移动i时，发现指针指向的值大于a时候，停止移动

移动j同理，当发现j指向的值小于a的时候，停止移动

此时i,j都判断到了不符合的数，对于他们不符合的数来说

不符合i指针的数符合j的指针，不符合j指针的数符合i的指针，

我们将i,j指向的数交换位置，就可以了

两个指针相遇的时候，i指针经过的数一定小于x

j指针经过的数一定小于y

模板

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll n;
const int N =1e6+10;
ll q[N];
void kpai(ll q[],int l,int r)//函数开始
{//判断一下如果左右边界大小错误，或者相等，则这个序列已经排完了，returnif(l==r)return;//随便选一个a,为分界点ll a=q[(r+l)/2];//不直接使用lr,是因为下面分割的时候lr还有用//定义i,j,为指针，因为下方是先++再循环，为了配合do while，指针向边界外再移动一格//i是左指针，向外移动一格为-1，j是右指针，向外移动一格为+1ll i=l-1; int j=r+1;//如果i,j相遇，结束循环while(i<j){//先++,再判断循环，如果while遇到i指向的数不小于a，结束循环，j同理//绝对不会死循环，因为判断里没有<=和>=,所以遇见a本身时，一定会停止，没有死循环do i++;while(q[i]<a);do j--;while(q[j]>a);//当循环停止，一定是ij都发现了不符合自己判断条件的数，并且正在指向他//因为至少会发现a,所以一定会停止循环，且交换和a相等的数，也符合预期效果//不符合i的数一定符合j，不符合j的数一定符合i(a除外，他既不符合i也不符合j)//当然，这个过程会导致和a相等的数互换,但是相等的数不影响排序，只是影响一点点速度//a是序列中间的一个值，序列被a划分为两段//如果i>j了，说明左右分界的两段，都已经被遍历过了//现在的情况，符合前面设想的，分阶点左右两边，都一致的小于a或者大于aif(i<j)swap(q[i],q[j]);}//上面的循环结束，证明此时i，j,已经相遇 ,i经过的数一定小于等于a，j经过的数一定大于等于a//把i经过的一段数和b经过的一段数，都看成一个整体，这两段数已经排好序了//我们把i或者j取出来一个，当做分界点//这个分界点和a的分界点不同，a的分界点目的是利用a进行比较大小进行排序//这个分界点的作用是将一段数分成两段，然后再在每段里分别定义分界点a进行排序//这个分段的目的是经过不断的切分，最后把数据切割成最小的数据段，就是一个数//一个数，再进入嵌套的函数的时候，会因为第一个if判断，l==r,而停止循环//在一个数之前，是两个数，或者三个数，将两个数排好顺序，放回在有子串顺序的父串内//假如两个数的父串是四个数，两个数据段，两个数据段是已经排好序了//两个数据段内自己的两个数，经过排序，再放回父串，那父串就是完整的排序后的数据串了//那再将父串放入父串的父串，父串的父串也是完整排序的数据串了//循环往复，数据串排序就结束了kpai(q,l,j);kpai(q,j+1,r);
}
int main(){scanf("%d",&n);//读入for(int i=0;i<n;i++){scanf("%lld",&q[i]);}//快排函数kpai(q,0,n-1);//读出for(int i=0;i<n;i++){cout<<q[i]<<' ';}return 0;
}