做网站的不给源文件怎么在百度上发布信息广告
快排的主要思想是分而治之
第一步,确定分界点,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;
}