八种常见排序方法总结 C/C++代码实现

目前评价排序算法的好坏标准主要有两点：
1.执行时间：高效的排序算法的比较次数和移动次数都应该尽可能的少。
2.辅助空间：算法执行期间所需要的辅助空间与待排序数据量无关。

1.冒泡排序

时间复杂度：
最好情况O(n)
最坏情况O(n²)
平均时间复杂度O(n²)
空间复杂度：
只需要一个变量作为辅助空间，空间复杂度O(1)
算法特点：
1.稳定排序。
2.移动的次数比较多，当初始记录无序，n较大时，算法不适用。

//冒泡排序
void Bubble_sort(int a[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        if(!flag) break;  //全程无交换，代表已经拍好序了
    }
}

2.插入排序

1.直接插入排序

时间复杂度：
最好情况O(n)
最坏情况O(n²)
平均时间复杂度O(n²)
空间复杂度：
只需要一个变量作为辅助空间，空间复杂度O(1)
算法特点：
1.稳定排序。
2.算法简单，容易实现。
3.n较大时，算法复杂度比较高，不易实现

void Insertion_sort(int a[],int n){
    int j;
    for(int i=1;i<n;i++){
        int temp=a[i];
        for(j=i;j>0&&a[j-1]>temp;j--)  a[j]=a[j-1];
        a[j]=temp;
    }
}

2.折半插入排序

讲道理我觉得这个算法得二分操作毫无乱用，甚至会增加时间复杂度。
继承了直接插入排序得所有缺点，并且感觉无优点。

//折半插入排序
void BSInsertion_sort(int a[],int n){
    for(int i=1;i<n;i++){
        int temp=a[i];
        int l=0,r=i-1;
        while (l<r){
            int mid=(l+r)/2;
            if(temp<a[mid]) r=mid-1;
            else l=mid+1;
        }
        for(int j=i-1;j>=l;j--){
            a[j+1]=a[j];
        }
        a[l]=temp;
    }
}

3.希尔排序

时间复杂度：
最好情况O(nlog²n)
最坏情况O(nlog²n)
平均时间复杂度O(nlogn)
空间复杂度：
只需要一个变量作为辅助空间，空间复杂度O(1)
算法特点：
1.这种跳跃式得的移动导致算法不是很稳定
2.这个增量序列有各种不同的取法Hibbard增量和sedgewick增量，据说这两种序列会降低其算法复杂度
3.n较大时，效果越明显，适用于n较大的情况

//希尔排序
void Shell_sort(int a[],int n){
    int j;
    for(int k=n/2;k>0;k/=2){
        for(int i=k;i<n;i++){
            int temp=a[i];
            for(j=i;j>=k&&a[j-k]>temp;j-=k)  a[j]=a[j-k];
            a[j]=temp;
        }
    }
}

4.选择排序

时间复杂度：
最好情况O(n²)
最坏情况O(n²)
平均时间复杂度O(n²)
空间复杂度：
只需要一个变量作为辅助空间，空间复杂度O(1)
算法特点：
1.是一种稳定的排序算法。
2.移动次数较少，每当一记录占用空间比较多的时候，这种排序比插入排序快

void Selection_sort(int a[],int n){
    for(int i=0;i<n;i++){
        int pos=i;
        for(int j=i+1;j<n;j++){
            if(a[j]<a[pos]) pos=j;
        }
        if(i!=pos) swap(a[i],a[pos]);
    }
    return;
}

5.堆排序

时间复杂度：
最好情况O(nlogn)
最坏情况O(nlogn)
平均时间复杂度O(nlogn)
空间复杂度：
只需要一个记录大小交换用的辅助空间，空间复杂度O(1)
算法特点：
1.是一种不稳定的排序算法。
2.建立堆所需要的比较次数比较多，因此记录数较少的时候不宜采用。

void heapify(int a[],int n,int node){
    if(node>=n) return;
    int l=2*node+1;
    int r=2*node+2;
    int imax=node;
    if(l<n&&a[l]>a[imax])  imax=l;
    if(r<n&&a[r]>a[imax])  imax=r;
    if(node!=imax){
        swap(a[imax],a[node]);
        heapify(a,n,imax);
    }
}
void build_heap(int a[],int n){
    int last_node=n-1;
    int fa=(last_node-1)/2;
    for(int i=fa;i>=0;i--){
        heapify(a,n,i);
    }
}
void Heap_sort(int a[],int n){
    build_heap(a,n);
    for(int i=n-1;i>=0;i--){
        swap(a[i],a[0]);
        heapify(a,i,0);
    }
}

6.归并排序

时间复杂度：
最好情况O(nlogn)
最坏情况O(nlogn)
平均时间复杂度O(nlogn)
空间复杂度：
只需要一个跟待排数组大小相同的辅助空间，空间复杂度为O(n)
算法特点：
1.是一种稳定的排序算法。
2.比较占用内存。

//归并排序
void Merge(int a[],int s,int mid,int e){
    int cnt=0;
    int temp[maxn];
    int pos1=s,pos2=mid+1;
    while (pos1<=mid||pos2<=e){
        if(pos1>mid) temp[cnt++]=a[pos2++];
        else if(pos2>e) temp[cnt++]=a[pos1++];
        else{
            if(a[pos1]<a[pos2]) temp[cnt++]=a[pos1++];
            else temp[cnt++]=a[pos2++];
        }
    }
    for(int i=0;i<e-s+1;i++){
        a[i+s]=temp[i];
    }
}
void Merge_sort(int a[],int s,int e){
    if(s<e){
        int mid=s+(e-s)/2;
        Merge_sort(a,s,mid);
        Merge_sort(a,mid+1,e);
        Merge(a,s,mid,e);
    }
}

7.快速排序

时间复杂度：
最好情况O(nlogn)
最坏情况O(n²)
平均时间复杂度O(nlogn)
空间复杂度：
执行时需要有一个栈来存放相应的数据，所以最大递归调用次数与递归树的深度一致，最好情况为O(logn)，最坏情况下为O(n)
算法特点：
1.是一种不稳定的排序算法。
2.是所有内部排序的最快的排序算法。
3.缺点较多，但是c++STL库中针对其缺点已经做出了优化。

int ipartition(int a[],int l,int r){
    int i=l;
    int temp=a[r];
    for(int j=l;j<r;j++){
        if(a[j]<temp){
            swap(a[i],a[j]);
            i++;
        }
    }
    swap(a[i],a[r]);
    return i;
}
void Quick_sort(int a[],int l,int r){
    if(l<r){
        int i=ipartition(a,l,r);
        Quick_sort(a,l,i-1);
        Quick_sort(a,i+1,r);
    }
}

8.基数排序

时间复杂度：
最好情况O(nk)
最坏情况O(nk)
平均时间复杂度O(nk)
*空间复杂度：**
空间复杂度（n+k）
算法特点：
1.是一种稳定的排序算法。
2.时间复杂度可以突破基数关键词比较一类方法的下界O(nlogn)达到O(n)
3.使用条件具有严格的要求。

//基数排序
int getnum(int x){
    if(x==0) return 1;
    int res=0;
    while (x){
        res++;
        x/=10;
    }
    return res;
}
void Radix_sort(int a[],int n){
    //找出最大的数
    int imax=a[0];
    for(int i=1;i<n;i++) imax=max(imax,a[i]);
    int len=getnum(imax);
    //核心操作
    //将元素放入桶中
    int divisor=1;
    for(int i=0;i<len;i++){
        vector<int> s[10];
        for(int i=0;i<10;i++) s[i].clear();
        for(int i=0;i<n;i++){
            int temp=a[i]/divisor%10;
            s[temp].push_back(a[i]);
        }
        //将桶中的元素放入数组
        int cnt=0;
        for(int i=0;i<10;i++){
            for(int j=0;j<s[i].size();j++){
                a[cnt++]=s[i][j];
            }
        }
        divisor*=10;
    }
}

数据结构算法学习文章被收录于专栏

算法学习记录