首页 > 其他分享 >排序

排序

时间:2024-01-25 20:24:09浏览次数:26  
标签:int namespace mid long msort 排序

排序

1.快速排序

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001];
void qsort(int l, int r)
{
   if(l>=r)return;  
   int i=l,j=r,x=a[l];
   while(i<j)
   {
   	    while(i<j&&a[j]>=x) j--;//从右向左找第一个小于x的数
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j &&a[i]<x)i++;//从左向右找第一个大于等于x的数
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
   }
   a[i]=x;
   qsort(l,i-1);//递归调用
   qsort(i+1,r);
}
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   qsort(1,n);
   for(int i=1;i<=n;i++)printf("%d ",a[i]);
   return 0;
}

2.归并排序

输入n(n<=10^5),再输入n个int范围内的整数,请把这n个数排序后输出。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[100010];
long long ans;
void msort(int L,int R)
{
   if(L==R)return;
   int mid=(L+R)/2;
   msort(L,mid);
   msort(mid+1,R);
   int i=L,j=mid+1,k=0;
   while(i<=mid && j<=R)
   {
      k++;
      if(a[i]<=a[j])b[k]=a[i],i++;
      else b[k]=a[j],j++;

   }
   for(int p=i;p<=mid;p++)
   {
       k++;
       b[k]=a[p];
   }
   for(int p=j;p<=R;p++)
   {
       k++;
       b[k]=a[p];
   }
    for(int p=1;p<=k;p++)a[L+p-1]=b[p];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    msort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);;
    return 0;
}

标签:int,namespace,mid,long,msort,排序
From: https://www.cnblogs.com/RTER/p/17988082

相关文章

  • MySQL SQL点查,范围查,排序,分组的Explain分析和SQL优化(8.0版本)
    MySQLSQL常用优化主要有where,range,order,groupby,or等查询。下图是优化的原则,后面会有一个例子来看看:比如建立了联合索引(c1,c2,c3),索引长度分别为5,5,4。数据有50条:点查SELECT*FROMtraining.t1wherec3=1andc2=1andc1=1;使用了索引,只要全部包含索引列,那么点查顺序......
  • 哈希排序
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,a[1000009];inlinevoidread(registerint&a){a=0;charc;while((c=getchar())<48);doa=(a<<3)+(a<<1)+(c^48);while((c=getchar())>47);}......
  • 归并排序
    归并排序  做法归并,基于分治,但是不同于快排1.确定分界点,这回的分界点是固定的,是mid。=2.排序左边和右边3.归并如图,红色箭头是该区间的最小值,假设答案数组res[]。如果A数组最小值比B数组最小值还小,把该值放入res[]。然后箭头向右移一位。继续这样比较一个区间全部值......
  • 快速排序
    快排 做法 快排,基于分治1.确定分界点,q[l],q[(l+r)/2],q[r],随机,四种都可以,但是推荐q[(l+r)/2]2.[重点]调整区间,划分2个区间,使得左半边所有的数<=x,右半边所有的数>=x,注意,x不一定在两个区间交界处,可能在很奇怪的位置3.递归处理左右两段 比较暴力的做法   先开......
  • KY207 二叉排序树C++
    考二叉搜索树的插入。#include<iostream>usingnamespacestd;structnode{intdata;structnode*left;structnode*right;};typedefstructnodetree;intmain(){intn;while(cin>>n){tree*root=NULL;while(n!=0......
  • 逆序对/归并排序
    逆序对定义:对于给定的一段正整数序列,逆序对就是序列中$a_i>a_j$且$i<j$的有序对。P1908逆序对-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2e6+10;intn,m,a[N],c[N],res,num;void......
  • 洛谷题单指南-模拟和高精度-P1786 帮贡排序
    原题链接:https://www.luogu.com.cn/problem/P1786题意解读:此题比较简单,模拟+排序即可解决。需要注意的是,当帮贡或者等级相同时,都要保持原来的顺序,因此需要记录每个人的编号,便于排序。话不多说,直接上代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;constint......
  • 冒泡排序
    冒泡排序//e.g.设计一个函数实现冒泡排序,将一个整型数组排序voidBubble_Sort(int*arr,intsz)//arr是数组,对数组传参,传的是首元素地址&arr[0]{ //确定bubble排序的趟数 inti=0; intcount=0; for(i=0;i<sz-1;i++) { intflag=1; intj=0; for......
  • 用Java实现冒泡排序:实用教程带你入门
    在处理一些特定系统功能时,经常需要使用冒泡排序。例如,在一个电子商务网站中,需要对商品进行排序和过滤。这个时候可以使用冒泡排序对商品进行排序,以便用户能够按照价格、销量、评分等不同字段进行排序。通过使用冒泡排序,系统可以提供更加灵活和个性化的排序选项,以便用户能够更加方便......
  • 冒泡排序、选择排序、二分查找
    1publicstaticvoidmain(String[]args){2//冒泡排序3//定义一个数组,存储一些数据4int[]arr={5,3,1,2,9,6};5System.out.println("=========冒泡排序==========");6//定义一个循环轮数7fo......