01-06 16:49 蒟蒻小学 算法工程师 发布于山东
关注
面试手撕题实例：快速排序这样写稳过
#一人分享一道面试手撕题#
来分享一个快速排序的实操代码，数组a[]，左边界l，右边界r。核心是partition函数：选a[r]当基准，用i标记小于基准的区域，遍历数组把小于基准的数交换到左边，最后把基准放到正确位置。递归处理左右子数组，几行代码就能搞定啦
int partition(int a[],int l,int r){
int p=a[r],i=l;
for(int j=l;j<r;j++)
if(a[j]<p)swap(a[i++],a[j]);
swap(a[i],a[r]);
return i;
}
void qsort(int a[],int l,int r){
if(l<r){
int m=partition(a,l,r);
qsort(a,l,m-1);
qsort(a,m+1,r);
}
}
来分享一个快速排序的实操代码，数组a[]，左边界l，右边界r。核心是partition函数：选a[r]当基准，用i标记小于基准的区域，遍历数组把小于基准的数交换到左边，最后把基准放到正确位置。递归处理左右子数组，几行代码就能搞定啦
int partition(int a[],int l,int r){
int p=a[r],i=l;
for(int j=l;j<r;j++)
if(a[j]<p)swap(a[i++],a[j]);
swap(a[i],a[r]);
return i;
}
void qsort(int a[],int l,int r){
if(l<r){
int m=partition(a,l,r);
qsort(a,l,m-1);
qsort(a,m+1,r);
}
}
全部评论
相关推荐
网易游戏公司福利 606人发布 
查看34道真题和解析 点赞 评论 收藏
分享