排序专题

发表于 | 分类于

排序专题

基本题面：

设有n个正整数，保证n不大于100且这n个数都不大于1000，对其进行从小到大的排序。

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=0;i<n;i++)//依次确定应该填在下标为i的位置的数
    {
        for(int j=i+1;j<n;j++)//将下标i上保存的数依次与其后所有数字比较
        {
            if(a[i]>a[j])
            {
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=0;i<n;i++)//通过第i次交换，能确定下标为i的位置所应该填写的数
    {
        for(int j=n-1;j>i;j--)//每次把最小的交换到最前面
        {
            if(a[j-1]>a[j])//比较相邻两个
            {
                int temp=a[j-1];
                a[j-1]=a[j];
                a[j]=temp;
            }
        }
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

桶排序

桶排序有其缺点：

1、必须全是整数（负数可以平移数轴）

2、必须知道数字最大不超过多少

3、所开数组不得超过题目的内存限制

需要以上三点同时满足，否则不可以使用桶排序 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
int main()
{
    int n,a[100];
    int bucket[1000]={0};//用bucket[i]表示数字i出现的次数，初始化为0
    //因为题目中说了都是正整数而且均小于1000，所以数组开到1000
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
    {
        int number=a[i];
        bucket[number]++;//每当数字i出现，就令其出现次数+1
    }
    for(int i=0;i<1000;i++)//因为题目中说了都是正整数而且均小于1000，所以循环小于1000
    {
        if(bucket[i]!=0)//如果bucket[i]==0，则表示数字i没有出现过，就不需要输出了
        {
            for(int j=0;j<bucket[i];j++)
            {
                //因为数字出现了bucket[i]次，所以需要循环bucket[i]次
                //否则会造成重复数字只会输出一个
                cout<<i<<" ";
            }
        }
    }
    return 0;
}

sort函数

sort函数默认是从小到大排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

如果要令sort函数实现从大到小排序，可以写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    if(a>b) return true;
    else return false;
}
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

其中cmp函数因为bool类型的特性，又可简写，变为如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

还可以有不写cmp函数，而使用重载运算符的方法。此处不做介绍，详见C++语言-9-结构体。

堆排序

堆排序需要使用优先队列，开始学习队列后才需要学习。

优先队列默认是最大堆，也就是说最大的数在队首。要实现从小到大排序的话只能写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    int n;
    priority_queue<int,vector<int>,greater<int> >q;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        q.push(t);
    }
    for(int i=0;i<n;i++)
    {
        cout<<q.top()<<" ";
        q.pop();
    }
    return 0;
}

而若要用优先队列实现从大到小排序，只需写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    int n;
    priority_queue<int>q;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        q.push(t);
    }
    for(int i=0;i<n;i++)
    {
        cout<<q.top()<<" ";
        q.pop();
    }
    return 0;
}

快速排序

快速排序是分治算法的入门题，开始学分治算法后才需要学习。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
using namespace std;
void kuai(int l,int r)//每次确定区间最中间的数字
{
    int i=l,j=r,mid=a[(l+r)/2];
    while(i<=j)
    {
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            int tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
            i++;
            j--;
        }
    }
    if(l<j) kuai(l,j);//排序左区间
    if(r>i) kuai(i,r);//排序右区间
}
int main()
{
    int n,a[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    kuai(0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

--It's the end.Thanks for your read.--