第三步递归处理左右两段

{//判断一下如果左右边界大小错误或者相等则这个序列已经排完了returnif(lr)return;//随便选一个a,为分界点ll

aq[(rl)/2];//不直接使用lr,是因为下面分割的时候lr还有用//定义i,j,为指针因为下方是先再循环为了配合do

while指针向边界外再移动一格//i是左指针向外移动一格为-1j是右指针向外移动一格为1ll

il-1;

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

i0;in;i){scanf(%lld,q[i]);}//快排函数kpai(q,0,n-1);//读出for(int

i0;in;i){coutq[i]