基础算法(一)快速排序
算法思想
通过一个分界值x,将序列分为大于x和小于x的两部分(注意,此分界值不一定是在序列中点,而是随便选取),然后再递归处理这左右两部分,直到x左边的值都小于等于x,x右边的值都大于等于x,这样我们就得到了一个排好序的有序序列。
代码模板
void quick_sort(int l,int r) //对q数组区间[l,r]的序列排序
{
if(l>=r) return; //若l==r,区间长度为1,则返回
int x=q[l+r>>1],i=l-1,j=r+1; //设定分界值x(通常取两边或中点)
//注意i,j初始值在两端点之外
while(i<j)
{
do i++;while(q[i]<x); //一直在左边找,直到找到大于等于x的数
do j--;while(q[j]>x); //一直在右边找,直到找到小于等于x的数
if(i<j)
swap(q[i],q[j]); //交换这两个数,这样一来刚刚大于等于x的数就跑到右边了,小于等于x的数就跑到左边了
}
quick_sort(l,j); //递归左右两边序列
quick_sort(j+1,r);
}
时间复杂度分析