排序总结

写在前面

排序是最基础的东西啦，一定要记板子！记板子！记板子

目录

一、选择排序

二、冒泡排序

三、插入排序

四、桶排序

五、快速排序

六、归并排序

七、堆排序

 

---

 

一、选择排序

1.操作

每一趟从待排序的数据元素中选出最小（或最大）的一个元素放到待排序的序列的最前面，直到所有元素都排序完毕。

2.特点

<1>稳定性：不稳定

<2>时间复杂度：O(n²)

<3>辅助空间：O(1)

3.应用

n较小，且对稳定性无要求时宜用选择排序。

4.代码实现

#include<iostream>
using namespace std;
int a[100],n;
int main(){
    int num,mid;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        num=i;
        for(int j=i+1;j<=n;j++)
            if(a[j]<a[num]) num=j;//找出最小的元素
        if(num!=i){
            mid=a[i];
            a[i]=a[num];
            a[num]=mid;
        }//把最小的元素排到前面
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

go back

---

 

二、冒泡排序

1.操作

两层循环每次把最大的数排到最后，像气泡上升。

2.特点

<1>稳定性：稳定

<2>时间复杂度：O(n²)，最好为O(n)

<3>辅助空间：O(1)

3.应用

待排序的序列整体或局部有序时能达到较快的速度。n较小，且对稳定性有要求时宜用冒泡排序。

4.代码实现

#include<iostream>
using namespace std;
int a[100],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    bool change;
    for(int i=n-1;i>=1;i--){
        change=1;//使用布尔变量判断是否要交换
        for(int j=1;j<=i;j++)
            if(a[j]>a[j+1]) swap(a[j],a[j+1]),change=0;
        if(change) break;
//如果没有交换就说明已经是有序的，直接退出以减少排序次数（主要针对局部或整体有序的序列）
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
} 

go back

---

 

三、插入排序

1.操作

当读入一个元素时，在已经排好序的序列中，搜寻它正确的位置，再插入读入的元素。（注意：插入前要把后面所有的后移一位）

2.特点

<1>稳定性：稳定

<2>时间复杂度：O(n²)，最好为O(n)

<3>辅助空间：O(1)

3.应用

待排序的序列整体或局部有序时能达到较快的速度。n较小，且对稳定性有要求时宜用插入排序。

4.代码实现

#include<iostream>
using namespace std;
int n,a[100];
int main(){
    cin>>n;
    int mid;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1,j;i<=n;i++){//现在要插入第i个元素
        for(j=i-1;j>=1;j--)
            if(a[j]<a[i]) break;//在i位置前面的有序区间中找a[i]应该所在的位置
        if(j!=i-1){
            mid=a[i];
            int k;
            for(k=i-1;k>=j;k--)
                a[k+1]=a[k];//后移
            a[k+1]=mid;//把a[i]放到正确的位置上
        }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
} 

go back

---

 

四、桶排序

1.操作

若待排序值在一个明显有限范围内（整型）时，可设计有限个有序桶，待排序的值装入对应的桶（每个桶可以装入若干个值），桶号就是待排序的值，按顺序输出各桶的值就可以得到有序序列。

2.特点

<1>稳定性：不稳定

<2>时间复杂度：O(n)

<3>辅助空间：O(n) (用空间换时间)

3.应用

若待排序的记录的关键字在一个明显有限范围内且空间允许时宜用桶排序。

4.代码实现

#include<iostream>
#include<cstring>
using namespace std;
int main(){
    int b[100],n,k;//b为桶
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        b[k]++;//把等于k的元素全部装进编号为k的桶里
    }
    for(int i=0;i<=100;i++){
        while(b[i]>0){
            cout<<i<<" ";
            b[i]--;
        }
        cout<<endl;
    }
    return 0;
}

go back

---

 

五、快速排序

1.操作

快速排序是对冒泡排序的一种改进。通过一趟排序将待排序序列记录分割成独立的两部分，其中一部分记录的关键字皆比另一部分小，则可分别对这两部分进行排序。(二分的思想)

2.特点

<1>稳定性：不稳定

<2>时间复杂度：O(nlog2n)，最坏为O(n²)

<3>辅助空间：O(log2n)，最坏为O(n)

3.应用

快排在待排序的序列整体或局部有序时反而慢了。n较大，元素随机，且对稳定性无要求时宜用快速排序。

4.代码实现

一般来说直接用sort就可以啦……QWQ

#include<iostream>
using namespace std;
void qsort(int,int);
int a[100],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}
void qsort(int l,int r){
    int mid=a[(l+r)/2];//定义当前区间中间的数为分隔数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//如果左边的数<分隔数，则继续找
        while(a[j]>mid) j++;//如果右边的数>分隔数，则继续找
        if(i<=j){
            swap(a[i],a[j]);//交换两个不符合条件的数
            i++;j--;//继续找
        }
    }while(i<=j);
    if(l<j) qsort(l,j);//分割成左右两个区间再继续找
    if(i<r) qsort(i,r);
    return;
} 

go back

---

 

六、归并排序

1.操作

先使每个子序列有序，再使子序列段区间有序。

2.特点

<1>稳定性：稳定

<2>时间复杂度：O(nlog2n)

<3>辅助空间：O(n)

3.应用

可以解决逆序对问题。

4.代码实现

#include<bits/stdc++.h>
using namespace std;
int a[100],ans[100];
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=l;//合并
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            ans[k]=a[i];k++;i++;
        }
        else{
            ans[k]=a[j];k++;j++;
        }
    }
    while(i<=mid){//复制左边子序列剩余
        ans[k]=a[i];
        k++;
        i++;
    }
    while(j<=r){//复制右边子序列剩余
        ans[k]=a[j];
        k++;
        j++;
    }
    for(i=l;i<=r;i++)
        a[i]=ans[i];
}
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    msort(1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

这里再放一个求逆序对的代码吧QWQ

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=l;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            r[k]=a[i];k++;i++;
        }
        else{
            r[k]=a[j];k++;j++;
            ans+=mid-i+1;//统计产生逆序对的数量
//右边区间在合并过程中如果是较小的值，那么它和左边区间剩余的元素就存在逆序对关系
        }
    }
    while(i<=mid){
        r[k]=a[i];k++;i++;
    }
    while(j<=r){
        r[k]=a[j];k++;j++;
    }
}

go back

---

 

七、堆排序

1.操作

利用大(小)根堆的性质排序。

2.特点

<1>稳定性：不稳定

<2>时间复杂度：O(nlog2n)

<3>辅助空间：O(1)

3.应用

n较大，并且元素本身可能有序，对稳定性无要求时宜用堆排序。

4.代码实现

对于堆的操作主要就是两个，一个是插入，一个是删除，这里先放一个插入操作的核心代码，提供不用STL和使用STL两个版本

//插入元素
void put(int d){//将元素d加入堆中
    int now,next;
    heap[++heap_size]=d;//先放到堆底
    now=head_size;
    while(now>1){//heap[1]是堆顶
        next=now>>1;
        if(heap[now]>=heap[next]) break;
//堆是完全二叉树，性质：左二子的编号是父亲的两倍，右儿子的编号是父亲的两倍加一
        swap(heap[now],heap[next]);
        now=next;
    }
}

//使用STL的版本
void put(int d){
    heap[++heap_size]=d;
    //push_heap(heap+1,heap+heap_size+1);    //大根堆
    push_heap(heap+1,heap+heap_size+1,greater<int>());//小根堆
}

下面的是删除操作的核心代码，同样有不用STL和使用STL两个版本

//取出并删除元素
int get(){
    int now,next,res;
    res=heap[1];//取出最小元素，即小根堆的堆顶
    heap[1]=heap[heap_size--];//把最后一个元素放到堆顶
    now=1;
    while(now*2<=head_size){//调整堆的排列
        next=now*2;
        if(next<heap_size&&heap[next+1]<heap[next]) next++;
        if(heap[now]<=heap[next]) break;
        swap(heap[now],heap[next]);
        now=next;
    }
    return res;
}

//使用STL的版本
int get(){
    //pop_heap(heap+1,heap+heap_size+1);     //大根堆
    pop_heap(heap+1,heap+heap_size+1,greater<int>());
    return heap[heap_size--];
}

go back