名言开头 (不要问我是谁说的)

排序过程，可以将无序的杂乱无章的东西整理清楚，便于查询统计和利用。

例1 选举学生会

让投票过程“自行完成排序”。放n个投票箱，投票人支持谁就投谁。
后只需统计每个投票箱中有几张选票，即可完成。代码如下：

#include <iostream>
using namespace std;
int a[1010]={0},n,m,tmp;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>tmp;
        a[tmp]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<a[i];j++)
            cout<<i<<' ';
    cout<<endl;
    return 0;
}

这种排序方法被称为计数排序。
读入选票并统计的时间复杂度是 O(m)，输出的时间复杂度是 O(m+n)，空间复杂度是 O(n)。
所以排序算法只能用于排序编号不是很大的情况。
不过也有改进方法比如桶排序和基数排序，他们都不依赖于排序对象的大小比较。

例2 输入n (n<1000)个数字a[i] (a[i]<10^9)，将其排序后输出。
数据范围有点大。。。计数排序肯定不行了。
读者可以先假设你要把3 2 8 6 2的牌排序，看能不能想到多种方法。

前方高能！！

做完才能往下翻~

我们继续看，
solution 1:
从第一张开始找最小的牌，放在最前面；
从第二张之后再找最小的一张……以此类推。
代码如下：

for(int i=0;i<n-1;i++)
    for(int j=i+1;j<n;j++)
        if(a[j]<a[i])
            swap(a[i],a[j]);

solution 2:
若把大的放在后面呢？可以倒过来使用选择排序，
有没有别的方法呢？有的，比较第1和第2，若第2大于第1，
则交换位置；然后是第2和第3……然后继续新的一轮
经过n-1轮后，就排好了，代码如下：

for(int i=0;i<n-1;i++)
    for(int j=0;j<n-i-1;j++)
        if(a[j]>a[j+1])
            swap(a[j],a[j+1]);

这就是冒泡排序。他的时间复杂度是O(n^2)，空间复杂度是O(n),还是没有改进。
补：有一种改良版叫希尔排序 。
solution 3:
把牌分为两区，有序&无序。最开始有序只有第一张牌。
要把“无序区”不停的插入到“有序区”中，代码如下：

for(int i=1;i<n;i++)
{
    int now=a[i],j;
    for(j=i-1;j>=0;j--)
        if(a[j]>now)
            a[j+1]=a[j];
    else break;
    a[j+1]=now;
}

这叫插入排序，算法复杂度还是O(n^2)，空间复杂度也都一样。
以上三种一般不会再竞赛中用到，但需要了解。
END