算法（9）-计数排序-桶排-(C++)

     冒泡、选择、插入、堆排、归并、荷兰国旗、快排等都是基于比较的排序。桶排是根据数据状况做的计数排序，在range少，比如年龄（1-200），数据多的时候非常好用。如果你理解词频统计，那么就能理解什么是桶排。时间复杂度为O(N)。

步骤：
     1.取最大值，其余补足位数  比如最大值为100  23->023
     2.建10个队列，就是10个桶 分别对应数字[0-9]
     3. for() 个位 十位 百位..进队列排 就是按个、十、百、千...有序，最后数字就有序了。
           3.1.d=1 个位  统计数字  从左到右
             比如数组是[ 022，021， 032， 031， 001， 100]
                       1 3 2 0 0 0 0 0 0 0 
               count[0 1 2 3 4 5 6 7 8 9]  含义为个位上每个数有几个
          3.2 统计每位上 <<=0 《=1有几个  从左到右
                    1 4 6 6 6 6 6 6 6 6
          count`[0 1 2 3 4 5 6 7 8 9] 
         3.3 进桶     从右到左
              0~0 上一个 搞定0位置  100
              0~3 上4个  搞定3位置  001
              0~2 上3个  搞定2位置
        3.4出桶  复制回原来的数组 从左到右

上代码

//取相应的位数
int getDigit(int x, int d) {
    return ((x / ((int)pow(10, d - 1))) % 10);
}

void radixProcess(int arr[], int m_num, int begin, int end, int digit)
{
    int radix = 10;//固定的 长度为[0..9]
    int i = 0, j = 0;

//  int* bucket = new int[m_num+1];//有多少数就准备个多大的辅助空间
    int bucket[11] = {0};
    for (int d = 1; d <= digit; d++) //有多少位就进出几次 d=1表示个位 =2表示十位 =3表示百位 
    {
        //int* count = new int[radix];   //统计数组 ，长度为[0..9] 每次都是10个
        int count[10] = {0};
        //1.取得每个数组值每位的值   遍历次数 数组个数，从左往右， 取得每个数组值每位的值
        for (i = begin; i <= end; i++)
        {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        //2.统计《=0，《=1 值，0-9   遍历10次 0-9  从左往右  位数字统计   <=0 《=1总共有有几个
        for (i = 1; i < radix; i++)
        {
            count[i] = count[i] + count[i - 1];
        }
        //3.遍历次数 ，数组个数， 从右往左，把值放入bucket[]中  
        //数组值进辅助空间
        for (i = end; i >= begin; i--)
        {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        //4.拷贝回原数组
        for (i = begin, j = 0; i <= end; i++, j++)
        {
            arr[i] = bucket[j];
        }
    }

}


// 取最大值 得到位数
int maxbits(int arr[],int m_num) {
    int max =0 ;
    for (int i = 0; i < m_num; i++) {
        max=(max>arr[i])? max: arr[i];
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

void radixSort_main(int arr[], int m_num)
{
    cout << "radixSort******************" << endl;
    if (arr == NULL || m_num < 2) { return; }
    radixProcess(arr, m_num,0, m_num - 1, maxbits(arr, m_num));
    for (int i = 0; i < m_num; i++)
    {
        cout << arr[i] << endl;
    }

}