计数排序和基数排序

这两个排序一起写是因为基数排序里面调用了基数排序。

首先两个排序都是针对整数的排序，时间复杂度都是O(n)

1.计数排序：

  计数排序的主要思想就是数出数组中比数m小的数的个数，推算出m排序后的位置，例如数组2 5 3 0 2 3 0 3，我们从小到大数出有2个0，2个2，3个3和1个5.所以两个0放在第一位和第二位上，两个2放在接下来的第3，4位上，依次类推。

  算法代码主要分为3个循环，第一个循环数出待排序数组中各个数有几个，第二个循环计算出每个数的位置，第三个循环把每个数放到对应的位置上。代码如下：

#include <iostream>
using namespace std;

void counting_sort(int a[8],int b[8])
{
    int c[6] = {0};
    //第一个循环，数出a中各个数的数目
    for(int i = 0;i < 8;i++)
        c[a[i]] = c[a[i]] + 1;

    //第二个循环，计算a中各个数排序后的位置
    for(int i = 1;i < 6;i++)
        c[i] = c[i-1]+c[i];

    //第三个循环，把每个数放到正确的位置上
    for(int i = 7;i >= 0;i --){
        b[c[a[i]]-1] = a[i];  //注意这里一定要-1！！因为b的下标是从0开始的！
        c[a[i]] --;
    }

}
int main()
{
    int a[8] = {2,5,3,0,2,3,0,3};
    int b[8] = {0};

    counting_sort(a,b);

    for(int i = 0;i < 8;i ++)
        cout << b[i]<<" ";

    cout <<endl;
}

2. 基数排序

   基数排序适用于位数比较多的数。它先根据每个数的最低位排序，然后根据次高位排序，依次类推。例如，下图中7个三位数，使用基数排序的过程如下：

上述例中的基数排序中还调用了排序算法分别根据所有数据的每一位对他们排序，这个排序算法一定要是稳定的，因为对高位排序的时候，要保证之前对低位排序的结果保留下来。下面的代码中我在while循环中每次都用了计数排序。虽然基数排序要调用多次计数排序，但相对于待排序的数的数量来说，数的位数总是一个常量，所以基数排序仍然是一个线性时间复杂度的排序。在radix_sort()函数中有一个参数BASE，这代表进制。上述的图列举的是十进制下的基数排序。但我们同样可以用二进制下的基数排序，并且由于取模运算是一个耗时运算，而移位运算耗时较短，所以通常二进制下的基数排序速度更快。下面的例子说明了二进制的基数排序过程：

代码如下（主函数中调用的是二进制的基数排序，如果用移位来写会更快，取模是比较慢的运算）：

#include <iostream>
using namespace std;

void radix_sort(int a[7],int BASE)
{
    int maxx = a[0];
    int exp = 1;
    int b[7] = {0};

    //找出数组中最大的元素作为判断循环次数的依据
    for(int i = 1;i < 7;i ++)
        if(a[i] > maxx)
            maxx = a[i];
    while(maxx/exp > 0)
    {
        int c[10] = {0};
        for(int i = 0;i < 7;i++)
            c[(a[i]/exp)%BASE] = c[(a[i]/exp)%BASE] + 1;

        //第二个循环，计算a中各个数排序后的位置
        for(int i = 1;i < BASE;i++)
            c[i] = c[i-1]+c[i];

        //第三个循环，把每个数放到正确的位置上
        for(int i = 6;i >= 0;i --){
            b[c[(a[i]/exp)%BASE]-1] = a[i];  //注意这里一定要-1！！因为b的下标是从0开始的！
            c[(a[i]/exp)%BASE] --;
        }

        //把b复制给a
        for(int i =0;i < 7;i++)
            a[i] = b[i];
        exp = exp * BASE;
    }
}
int main()
{
    int a[7] = {329,457,657,839,436,720,355};
    radix_sort(a,2);

    for(int i = 0;i < 7;i ++)
        cout << a[i]<<" ";

    cout <<endl;

}