排序算法

kevinf · 2025-07-19 09:57:16 · 算法·理论

排序算法

总览

1.选择排序

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int minn=2e9,num=-1;
        for(int j=i;j<=n;j++){
            if(a[j]<minn) num=j;
            minn=min(a[j],minn);

        }
        swap(a[i],a[num]);
    }

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    puts("");
    return 0;
}

2.冒泡排序

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<n;j++){
            if(a[j]>a[j+1]) swap(a[j],a[j+1]);
        }
    }

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    puts("");
    return 0;
}

优化#1

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        bool flag =false;
        for(int j=1;j<n;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        if(!flag) break;
    } 

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    puts("");
    return 0;
}

3.插入排序

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int i,j;
    for(i=1;i<=n;i++){
        for(j=0;j<i;j++){
            //找 
            if(a[j]>a[i]){
                break;
            }
        }
        //插入 
        if(j!=i){
            int t=a[i];
            for(int k=i-1;k>=j;k--){
                a[k+1]=a[k];

            } 
            a[j]=t;

        }
    } 

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    puts("");
    return 0;
}
}

4.桶排序

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        int num;
        scanf("%d",&num);
        a[num]++; 
    }
    for(int i=0;i<=1000;i++){
        for(int j=0;j<a[i];j++)
            printf("%d ",i);
    }
    puts("");
    return 0;
}

5.归并排序

#include<iostream>
using namespace std;
int a[110],b[110];
int n; 

void merge(int l,int r){
    if( l >= r ) return;
    int mid = (l+r)>>1;

    //拆
    merge(l,mid);
    merge(mid+1,r);

    //合
    int i=l,j=mid+1,k=0;
    while( i<=mid && j<=r ){
        if( a[i] <= a[j] ) b[++k] = a[i],i++;
        else b[++k] = a[j],j++;
    }

    while(i<=mid) b[++k] = a[i],i++;
    while(j<=r) b[++k] = a[j],j++;

    for(int i=1;i<=k;i++){
          a[l+i-1] = b[i];
    }   
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }       
    //归并排序
    merge(1,n);

    //输出    
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";

    return 0;
}

6.快速排序

#include<iostream>
using namespace std;
int a[110],b[110];
int n; 
int partition( int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort( int low, int high) {
    if (low < high) {
        int pi = partition( low, high);
        quickSort( low, pi - 1);
        quickSort( pi + 1, high);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }       
    quickSort(1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

7.计数排序

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];

int main(){
    int n,mx=-2e9;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
        mx=max(mx,a[i]);
    }

    for (int i = 1; i <= mx; ++i) cnt[i] += cnt[i - 1];
    //保证稳定性 
    for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];

    for(int i=1;i<=n;i++) printf("%d ",b[i]);
    return 0;
}

8.基数排序

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];
int n,mx=-2e9;
void fun(int res){
    memset(b,0,sizeof(b));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        cnt[a[i]/res%10]++;
    }
    for(int i=1;i<=9;i++){
        cnt[i]+=cnt[i-1];
    }
    for(int i=n;i>=1;i--){
        b[cnt[a[i]/res%10]--]=a[i];
    }
    for(int i=1;i<=n;i++){
        a[i] =b[i]; 
    } 
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
        mx=max(mx,a[i]);
    }
    for(int res=1;mx/res>0;res*=10){
        fun(res);
    }

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

9.堆排序

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];
int n;
//调整子树 
void heap_add(int root,int len){
    int mx=root,l=root*2,r=root*2+1;
    //如果左右孩子存在
    if(l<=len&&a[l]>a[mx]) mx=l;
    if(r<=len&&a[r]>a[mx]) mx=r;
    if(mx!=root){
        swap(a[root],a[mx]);
        heap_add(mx,len);
    }
}
void heap_sort(){
    //构建大顶堆
    for(int i=n/2;i>=1;i--){
        heap_add(i,n);
    } 
    for(int i=n;i>1;i--){
        swap(a[1],a[i]);
        heap_add(1,i-1);
    }
}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    heap_sort();

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}