排序补充(计数基数排序)

void CountSort(int *a , size_t size)
{
    int max = a[0], min = a[0];
    for (int i =1; i < size; ++i)
    {
        if (max < a[i])
        {
            max = a[i];
        }
        if (min > a[i])
        {
            min = a[i];
        }
    }
    int index = 0;
    int *CountArray = new int[max - min + 1];
    memset(CountArray, 0, sizeof(int)*(max - min + 1));
    for (int i = 0; i < size; ++i)
    {
        CountArray[a[i] - min]++;
    }
    for (int i = 0; i < max - min + 1; ++i)
    {
        for (int j = 0; j < CountArray[i]; ++j)
        {
            a[index++] = i + min;
        }
    }
}

所谓的基数排序原理就和哈希表极像,适合使用在待排序的数都处在一个比较小的范围内,开辟好一定的辅助空间,按照直接定址法,将辅助空间对应的位置的计数增加,最后排序的时候只要把之前建好的辅助数组遍历输出一遍就好了

int GetMaxDigit(int *a,size_t size)
{
    int digit = 1;
    int max = 10;
    for (int i = 0; i < size; ++i)
    {
        while (a[i] >= max)
        {
            digit++;
            max *= 10;
        }
    }
    return digit;
}

//一共需要几个数组呢?一个count,一个start还有一个收集用的暂存数组?最后拷贝回去就可以了!
void DigitSort(int *a, size_t size)
{
    int MaxDigit = GetMaxDigit(a, size);
    int curDigit = 1;
    int digit = 0;
    int Count[10];
    int Start[10];
    int *Bucket = new int[size];
    while (digit < MaxDigit)
    {
        memset(Count, 0, sizeof(int) * 10);
        memset(Start, 0, sizeof(int) * 10);
        for (int i = 0; i < size; ++i)
        {
            int num = a[i] / curDigit % 10;
            Count[num]++;
        }
        Start[0] = 0;
        for (int i = 1; i < 10; ++i)
        {
            Start[i] = Start[i - 1] + Count[i - 1];
        }
        for (int i = 0; i < size; ++i)
        {
            int num = a[i] / curDigit % 10;
            Bucket[Start[num]++] = a[i];
        }
        memcpy(a, Bucket, sizeof(int)*size);
        digit++;
        curDigit *= 10;
    }
}

基数排序又被称为桶排序,这里的代码例子是完成一个几位数的排序,可以看成先根据个位的数大小进行一次排序(扔进各自数的桶里(桶当然是有序的(0-9嘛)))然后进行按序收集,然后根据十位数扔进桶里,直到最高位

排序补充(计数基数排序)

这里我并未使用类似的链表结构,而是采用一个顺序表

排序补充(计数基数排序)

不停地往后存,使用count辅助数组进行计数(对应的0-9有几个数),使用start数组计算每个待排序的数在上图数组中的位置,上图的数组就相当于收集了

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/61d22d9d4df0f3e0ab60dabb56c3d243.html