今天学习了y总的两个排序模板,在此写一下算是回顾
第一次写,不太清楚,如果有错误也麻烦大家帮忙指正,感谢

首先是快速排序
快速排序的思想如下:
1:找到划分点,即与后面比较的数
可以是q[l],q[(l+r)/2],q[r],也可以是一个随机数
但是注意
划分点的选择是很重要的
如果你的划分点选择了q[l],那么对应的排序区间就应当是quick(q,l,j)和quick(q,j+1,r)
越界例子如下:
如果在我们的划分点选择了q[l]的情况下,选择将j替换成i-1的话,
那么假设此时只有两个数1,2
划分点为q[l]=1,i并没有小于q[l],停止在q[0]
而r=2>q[l],向前移动一位,此时q[l]和q[r]重合,即达到了l>=r将函数返回的条件
区间[l,i-1]此时i=0,发生越界问题
2:将区间划分成左右两部分(核心)
int i=l-1;int j=r+1;int x=q[l];
while(i[HTML_REMOVED]x);
if(i<j)
swap(q[i],q[j]);
}
如此我们便将数组根据划分点划分成了两个有序的小数组
3:递归调用quick划分两个小数组
quick(q,l,j);
quick(q,j+1,r);

然后是合并排序
合并排序和快速排序操作相反,先找到划分点,然后递归调用左右半边,使得左右半边有序
然后合并两个半边(核心),需要定义一个temp数组来接受合并后的值
1:划分点默认是中间值
int mid=q[(l+r)/2];
2:递归调用自身
merge(q,l,mid);
merge(q,mid+1,r);
3:合并
int i=l;
int j=mid+1;
int k=0;
while(i<=mid&&j<=r)
{
if(q[i]<q[j])
temp[k]=q[i];
else
temp[k]=q[j];

if(i<=mid)
temp[k++]=q[i];//处理完还剩下左半部分
if(j<=r)
temp[k++]=q[j];//处理完还剩下右半部分

}
4:将temp数组里面的内容放回到原来数组q[]中
for(i=l,k=0;i<=r;i,k)
q[i]=temp[k];