C++排序（一）——桶排序

大家好，我今天来介绍c++排序之——桶排序。

桶排序，是（我认为）最简单的排序，其原理很简单。

比如有5个数2，4，3，3，5，那么我们就建立一个数组n[6]，n[a]就代表这些数中有n[a]个a。

for(int i=0;i<6;i++){
    cin>>a;
    n[a]++;
}

在这样一个循环结束以后，n数组：

n[0]  n[1]  n[2]  n[3]  n[4]  n[5]
 0     0      1     2     1    1

这样，我们输出就可以了。

for(int i=0;i<6;i++) {
   //因为数列中有n[a]个a，所以输出n[a]个a即可
   for(j=1;j<=n[i];j++)
       cout<<i<<" ";
}

完整的模版代码如下：

#include<bits/stdc++.h>
using namespace std;
int n[此处填写排序数中最大的数以上的数]；
int a;//这是排序输入的数字。
int main(){
    for(int i=1;i<=排序的数的数量;i++){
         cin>>a;
         n[a]++;
    }
    for(int i=1;i<=排序数中最大的数;i++)
        for(j=1;j<=n[i];j++)
            cout<<i<<" ";
    return 0;
}

看，是不是很简单？但是，它也有它的缺点：每个数不能太大，不然会爆内存。

总结：桶排序，最简单的排序，但是排序的数不能太大，内存会爆。

PS：C++排序没有结束！我将会用4~5个博文把排序讲完。