文章

几种排序算法

快速排序

时间复杂度 O(nlogn) 稳定性 不稳定

void quicksort(int a[],int l,int r){
    int i=l;
    int j=r;
    int key=a[i];
    if(i>=j) return ;
    while(i<j){
        while(i<j&&key<=a[j]){
            j--;
        }
        a[i]=a[j];
        while(i<j&&a[i]<=key){
            i++;
        }
        a[j]=a[i];
    }
    a[i]=key;
    quicksort(a,l,i-1);
    quicksort(a,i+1,r);
    return ;
}

归并排序

时间复杂度 O(nlogn) 稳定性 稳定

void merge(int a[],int tmp[],int l,int mid,int r){//合并
    int i,nl=l,nr=mid+1,loc=l;
    while(nl<=mid&&nr<=r){
        if(a[nl]<a[nr]){
            tmp[loc++]=a[nl++];
        }else {
            tmp[loc++]=a[nr++];
        }
    }
    while(nl<=mid){
        tmp[loc++]=a[nl++];
    }
    while(nr<=r){
        tmp[loc++]=a[nr++];
    }
    for(i=l;i<=r;i++){
        a[i]=tmp[i];
    }
    return ;
}
void msort(int a[],int tmp[],int l,int r){//归并排序 
    if(l<r){
        int mid=l+(r-l)/2;//防止整数溢出 
        msort(a,tmp,l,mid);
        msort(a,tmp,mid+1,r);
        merge(a,tmp,l,mid,r);
    }
    return ;
}
void mergesort(int a[],int l,int r){//分配辅助数组空间
    if(l<r){
        int *tmp=(int *)malloc((r-l+3)*sizeof(int));
        msort(a,tmp,l,r);
    }
    return ;
}

冒泡排序

时间复杂度 O(n^2) 稳定性 稳定

void bubblesort(int a[],int l,int r){
    int i,j,t;
    for(i=l;i<r;i++){
        for(j=l;j<r-i+l;j++){
            if(a[j]>a[j+1]){
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
    return ;
}

选择排序

时间复杂度 O(n^2) 稳定性 不稳定

void selection_sort(int a[],int l,int r){
    int i,j,minn,t;
    for(i=l;i<r;i++){
        minn=i;
        for(j=i;j<=r;j++){
            if(a[minn]>a[j]){
                minn=j;
            }
        }
        t=a[minn];
        a[minn]=a[i];
        a[i]=t;
    }
    return ;
}

插入排序

时间复杂度 O(n^2) 稳定性 稳定

void insertion_sort(int a[],int l,int r){
    int i,j,t;
    for(i=l;i<=r;i++){
        t=a[i];
        for(j=i-1;j>=l;j--){
            if(a[j]>t){
                a[j+1]=a[j];
            }else {
                a[j+1]=t;
                break;
            }
        }
    }
    return ;
}

堆排序

时间复杂度 O(nlogn) 稳定性 不稳定 堆的性质:形状类似完全二叉树,大根堆每个结点都大于等于左右孩子,小根堆每个结点都小于左右孩子

//大根堆为例
void change(int a[],int p,int q){//交换p,q两个下标处的元素
    int tem;
    tem=a[p];
    a[p]=a[q];
    a[q]=tem;
    return ;
}
void heap(int a[],int t,int n){//交换后维护堆的性质
    int maxn;
    maxn=t;
    if(2*t<=n&&a[2*t]>a[maxn])  maxn=2*t;
    if(2*t+1<=n&&a[2*t+1]>a[maxn]) maxn=2*t+1;
    if(maxn!=t){
        change(a,maxn,t);
        heap(a,maxn,n);
    }
    return ;
}
void heapsort(int a[],int n){//大根堆 
    int i,maxn;
    for(i=n/2;i>=1;i--){//从第一个有孩子的结点开始 
        maxn=i;
        if(2*i<=n&&a[2*i]>a[maxn])  maxn=2*i;
        if(2*i+1<=n&&a[2*i+1]>a[maxn]) maxn=2*i+1;
        if(maxn!=i){//交换
            change(a,maxn,i);
            heap(a,maxn,n);
        }
    }   
    return ;
}

计数排序

特点和性质:通过计数而不是比较进行排序,适用于范围较小的整数序列 时间复杂度 O(n+k) 稳定性 稳定

void countsort(int a[],int l,int r){
    int n,i,j;
    if(r-l+1<=1) return ;
    n=r-l+1;//长度
    int maxn=a[l];
    for(i=1;i<=n;i++){
        maxn=max(a[i],maxn);
    } 
    int *tmp=(int *)malloc((maxn+1)*sizeof(int));//计数数组 
    int *count=(int *)malloc((maxn+1)*sizeof(int));//前缀和数组 
    int *tem=(int *)malloc((n+1)*sizeof(int));//辅助数组 
    memset(tmp,0,(maxn+1)*sizeof(int));
    memset(count,0,(maxn+1)*sizeof(int));
    memset(tem,0,(n+1)*sizeof(int));
    for(i=1;i<=n;i++){
        tmp[a[i]]++;
    }
    for(i=1;i<=maxn;i++){
        count[i]=count[i-1]+tmp[i];
    }
    for(i=l;i<=r;i++){
        tem[count[a[i]]]=a[i];
        count[a[i]]--;
    }
    for(i=l,j=1;i<=r;i++,j++){//复制到原数组 
        a[i]=tem[j];
    }
    return ;
}

希尔排序

时间复杂度 O(nlogn) 稳定性 不稳定

void shellsort(int a[],int n){
    int i,j,inc,key;
    for(inc=n/2;inc>=1;inc/=2){
        for(i=inc;i<=n;i++){
            key=a[i];
            for(j=i;j-inc>=1;j-=inc){
                if(a[j-inc]>key){
                    a[j]=a[j-inc];
                }else break;
            }
            a[j]=key;
        }
    }
    return ;
}
License:  CC BY 4.0