CPP教程-排序

C++教程

排序

在c++中,怎么样对一个无序数组从小到大/从大到小排序呢?

方法如下

1.函数法
c++本身就提供给我们一个高效的排序函数

int a[1000]//数据下标为1~n
sort(a+1,a+n+1)//若数据下标为0~n-1,则sort(a,a+n)

sort函数使用的方法是快速排序
2.选择排序

3.冒泡排序
程序如下

for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        if(a[j]>a[j+1])swap(a[j],a[j+1]);
    }
}

时间复杂度为O(n^2)
4.插入排序

5.快速排序(高级)
程序如下

int a[10000001],n;
void qsort(int l,int r){
    int mid=a[(l+r)/2],i=l,j=r;
    do{
        while(a[i]mid)j--;
        if(i<=j)swap(a[i++],a[j--]);
    }while(i<=j);
    if(l>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;
}

6.归并排序(高级)
程序如下

int a[10000001],n,b[10000001];
void msort(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    msort(l,mid);msort(mid+1,r);
    while(i<=mid&&j<=r){
        if(a[i]>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;
}