建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
温馨提示

抱歉,您需设置社区昵称后才能参与社区互动!

前往修改
我再想想

STAR联盟

话题 : 3 成员 : 21

加入HCSD

快速排序中的特殊位置

逾之 2022/1/10 104

快速排序中的特殊位置

  • 快排正常模板

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int i = l-1,j = r+1,x= q[l+r >>1];
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

  • 中间值的设置选择

  • 如果中间值设置为 mid = l + r >> 1;

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int i = l-1,j = r+1,mid = l+r >>1;
    while(i<j)
    {
        do i++;while(q[i]<q[mid]);
        do j--;while(q[j]>q[mid]);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

就会出现边界问题,例如跑样本

49 59 88 37 98 97 68 54 31 3

输出

3 49 59 37 88 31 54 68 97 98 
标准答案
3 31 37 49 54 59 68 88 97 98

回复 (0)

没有评论
上划加载中
标签
您还可以添加5个标签
  • 没有搜索到和“关键字”相关的标签
  • 云产品
  • 解决方案
  • 技术领域
  • 通用技术
  • 平台功能
取消

逾之

角色:校园大使

话题:1

发消息
发表于2022年01月10日 17:24:51 1040
直达本楼层的链接
楼主
倒序浏览 显示全部楼层
快速排序中的特殊位置

快速排序中的特殊位置

  • 快排正常模板

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int i = l-1,j = r+1,x= q[l+r >>1];
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

  • 中间值的设置选择

  • 如果中间值设置为 mid = l + r >> 1;

void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int i = l-1,j = r+1,mid = l+r >>1;
    while(i<j)
    {
        do i++;while(q[i]<q[mid]);
        do j--;while(q[j]>q[mid]);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

就会出现边界问题,例如跑样本

49 59 88 37 98 97 68 54 31 3

输出

3 49 59 37 88 31 54 68 97 98 
标准答案
3 31 37 49 54 59 68 88 97 98
点赞 举报
分享

分享文章到朋友圈

分享文章到微博

游客

您需要登录后才可以回帖 登录 | 立即注册