计数排序&基数排序(非比较排序)

1.计数排序
思路：相当于开个哈西表，表里存的是数字个数，数字做相对下标，以空间换时间。
特点：适合排范围集中的正数序列。
时间复杂度：O（n）
空间复杂度：O（1）

void CountSort(int *a,size_t size)
{
    assert(a);
    // 确定范围
    int max = a[0],min = a[0];
    for(size_t i = 0;i < size;++i)
    {
        if(a[i] > max)
            max = a[i];
        if(a[i] < min)
            min = a[i];
    }

    int range = max - min +1;
    int *CountArray = new int[range];
    memset(CountArray,0,sizeof(int)*range);
    for(size_t i = 0;i < size;++i)
    {
        CountArray[a[i] - min]++;
    }
    size_t index = 0;
    for(size_t i = 0;i < range;++i)
    {
        if(CountArray[i] != 0)
        {
            while(CountArray[i])
            {
                a[index++] = i + min;
                CountArray[i]--;
            }
        }
    }
    delete[] CountArray;
}

2.基数排序（LSD从低到高）

LSD-- Least Significant Digit first

MSD-- Most Significant Digit first

原理：先排低位，将低位相同的放在同一个“桶"中，再排高位，数列即有序。

void DigitSort(int *a, size_t size)
{
    int MaxDigit = GetMaxDigit(a, size);
    int curDigit = 1;
    int digit = 0;
    int Count[10];
    int *Start= new int[size];
    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]++;
        }

        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;
    }
    delete[] Bucket;
    delete[] Start;
}