基础算法AC1

基础算法AC1,第1张

基础算法AC1 快速排序
#include 
using namespace std;

const int N=1e6 + 10;//防止出现边界问题

int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
	if(l>=r) return;
	
	int x=q[(l+r)/2],i=l-1,j=r+1;//枢轴元素,可以选择q[l],q[r],中间元素或者一个随机值,要做相应调整
	while(ix);
		if(i 
归并排序 
#include 

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N],tmp[N];

void merge_sort(int q[],int l,int r)
{
    if(l >= r) return;
    
    int mid = (l+r)/2;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    
    int k=0, i=l,j=mid+1;
    while(i<=mid && j<=r)
    {
        if(q[i] <= q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i <= mid) tmp[k++]=q[i++];
    while(j <= r) tmp[k++]=q[j++];
    
    for(i = l,j = 0;i <= r;i ++,j ++) q[i] = tmp[j];
    
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++ ) scanf("%d",&q[i]);
    
    merge_sort(q,0,n - 1);
    
    for(int i = 0;i < n;i ++ ) printf("%d ",q[i]);
}
整数二分
#include 

using namespace std;

const int N=100010;

int m,n;
int q[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i>1;//先写上这个再决定要不要加1
            if(q[mid]>=x) r=mid;//判断条件
            else l=mid+1;
        }
        
        if(q[l]!=x) cout<<"-1 -1"<>1;//先写上这个再决定要不要加1
                if(q[mid]<=x) l=mid;
                else r=mid-1;
            }
            
            cout< 
浮点数二分 
//求正整数的平方根
#include 

using namespace std;

int main()
{
    double x;
    cin>>x;
    
    double l=0,r=x;
    while(r-l > 1e-6)//经验值,保留4位小数1e-6,保留5位小数1e-7,保留6位小数1e-8...
    //for(int i=0;i<100;i++)//或者无脑循环100次
    {
        double mid=(l+r)/2;
        if(mid * mid >=x) r=mid;
        else l=mid;
        
    }
    
    printf("%1fn",l);
    
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5691304.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存