| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1093 人关注过本帖
标题:数组下标和赋值的奇特问题(洛谷快速排序模板题卡了)
只看楼主 加入收藏
Divine
Rank: 2
等 级:论坛游民
帖 子:18
专家分:11
注 册:2019-11-17
结帖率:80%
收藏
已结贴  问题点数:10 回复次数:1 
数组下标和赋值的奇特问题(洛谷快速排序模板题卡了)
先上代码比较
程序代码:
#include<iostream>
using namespace std;
int arr[1000001],n;
void quicksort(int left,int right)
{
    
    int i=left;
    int j=right;
    int pivot=(left+right)/2;
    do
    {
        while(arr[i]<arr[pivot])
          i++;
          
        while(arr[j]>arr[pivot])
          j--;
        
        if(i<=j)
        {
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(left<j)
      quicksort(left,j);
    if(i<right)
      quicksort(i,right);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>arr[i];
    
    quicksort(1,n);
    for(int i=1;i<=n;i++)
      cout<<arr[i]<<" ";
    return 0;
}

这是40分的,wa了三个点
程序代码:
#include<iostream>
using namespace std;
int arr[1000001],n;
void quicksort(int left,int right)
{
    
    int i=left;
    int j=right;
    int pivot=arr[(left+right)/2];
    do
    {
        while(arr[i]<pivot)
          i++;
          
        while(arr[j]>pivot)
          j--;
        
        if(i<=j)
        {
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(left<j)
      quicksort(left,j);
    if(i<right)
      quicksort(i,right);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>arr[i];
    
    quicksort(1,n);
    for(int i=1;i<=n;i++)
      cout<<arr[i]<<" ";
    return 0;
}

这是ac的代码


比较发现是直接int pivot=arr[(left+right)/2];

先int pivot=(left+right)/2;再while(arr[i]<arr[pivot]),也就是放数组中的区别。

麻烦帮我看一下为什么?谢谢
搜索更多相关主题的帖子: while i++ int left cin 
2021-02-18 19:36
请输入密码
Rank: 2
等 级:论坛游民
威 望:5
帖 子:35
专家分:84
注 册:2020-11-19
收藏
得分:10 
第一个:swap后,可能会改变arr[pivot]的值。
第二个:pivot的值却不会被改变。

Bug易改,码风难移。
有事离开,无事灌水。
2021-02-18 20:52
快速回复:数组下标和赋值的奇特问题(洛谷快速排序模板题卡了)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030965 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved