松岗网站建设公司,济南网站制作案例,wordpress页面加上html,如何用电脑做网站快排的主要思想是分而治之
第一步#xff0c;确定分界点#xff0c;a
第二步#xff0c;调整区间#xff0c;利用分界点a#xff0c;把小于分界点a的数放在左边#xff0c;大于的放在右边#xff0c;相等的放在哪都可以
第三步#xff0c;递归处理左右两段
实现(暴… 快排的主要思想是分而治之
第一步确定分界点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
模板 #includecstdio
#includeiostream
#define ll long long
using namespace std;
ll n;
const int N 1e610;
ll q[N];
void kpai(ll q[],int l,int r)//函数开始
{//判断一下如果左右边界大小错误或者相等则这个序列已经排完了returnif(lr)return;//随便选一个a,为分界点ll aq[(rl)/2];//不直接使用lr,是因为下面分割的时候lr还有用//定义i,j,为指针因为下方是先再循环为了配合do while指针向边界外再移动一格//i是左指针向外移动一格为-1j是右指针向外移动一格为1ll il-1; int jr1;//如果i,j相遇结束循环while(ij){//先,再判断循环如果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划分为两段//如果ij了说明左右分界的两段都已经被遍历过了//现在的情况符合前面设想的分阶点左右两边都一致的小于a或者大于aif(ij)swap(q[i],q[j]);}//上面的循环结束证明此时ij,已经相遇 ,i经过的数一定小于等于aj经过的数一定大于等于a//把i经过的一段数和b经过的一段数都看成一个整体这两段数已经排好序了//我们把i或者j取出来一个当做分界点//这个分界点和a的分界点不同a的分界点目的是利用a进行比较大小进行排序//这个分界点的作用是将一段数分成两段然后再在每段里分别定义分界点a进行排序//这个分段的目的是经过不断的切分最后把数据切割成最小的数据段就是一个数//一个数再进入嵌套的函数的时候会因为第一个if判断lr,而停止循环//在一个数之前是两个数或者三个数将两个数排好顺序放回在有子串顺序的父串内//假如两个数的父串是四个数两个数据段两个数据段是已经排好序了//两个数据段内自己的两个数经过排序再放回父串那父串就是完整的排序后的数据串了//那再将父串放入父串的父串父串的父串也是完整排序的数据串了//循环往复数据串排序就结束了kpai(q,l,j);kpai(q,j1,r);
}
int main(){scanf(%d,n);//读入for(int i0;in;i){scanf(%lld,q[i]);}//快排函数kpai(q,0,n-1);//读出for(int i0;in;i){coutq[i] ;}return 0;
}
