计数排序:类似于桶排序,将待排序数组的元素的值通过对应关系对应为数组下标,对相同下标的值进行计数

特点

通过运算将待排序的元素的值作为下标,存放在临时的中间数组中,即需要申请内存大小=待排序元素的最大值-待排序元素的最小值+1,以容纳所有的待排序元素,另外该算法还需要一个用来对中间数组中重复的元素进行计数的数组,当添加元素时更新计数

基本逻辑

  1. 查找待排序元素的MAX元素值和MIN元素值
  2. 得出需要的内存len=MAX-MIN+1,并申请内存
  3. 将元素依次按照值-下标对应的方法(下标=元素值-MIN)填入中间数组并更新计数数组的值(自增1)
  4. 当所有元素都填入新数组后,排序完成,之后将排序的结果汇总将元素一个一个追加到有序数组中

注意:该算法在速度上比较稳定,但是对于内存,当待排序的数据分布不均匀,且差值较大时将浪费大量内存,因此在使用该算法时要注意内存的问题,如果需要排序浮点数则需要对修改由元素值计算出下标的方法,或对浮点数做特殊处理

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率还行
JSsort_1

该实现中需要调用者自己释放返回的数组指针所指向的内存

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    int MAX = 0, MIN = 0;
    for (size_t i = 0; i < numsSize; i++)
    {
        if (nums[i] > MAX)
        {
            MAX = nums[i];
        }

        if (nums[i] < MIN)
        {
            MIN = nums[i];
        }
    }

    size_t Medlen = (size_t)MAX - MIN + 1;
    int* Med = (int*)calloc(Medlen, sizeof(int));
    if (Med == 0)
    {
        return 0;
    }
    memset(Med, 0, Medlen * sizeof(int));

    size_t* Medcount = (size_t*)calloc(Medlen, sizeof(size_t));
    if (Medcount == 0)
    {
        return 0;
    }
    memset(Medcount, 0, Medlen * sizeof(size_t));

    for (size_t i = 0; i < numsSize; i++)
    {
        Medcount[nums[i] - MIN]++;
        Med[nums[i] - MIN] = nums[i];
    }

    //注意这里的内存要记得在函数外释放
    int* outA = (int*)calloc(numsSize, sizeof(int));
    if (outA == 0)
    {
        return 0;
    }
    memset(outA, 0, numsSize * sizeof(int));

    size_t outAp = 0;
    for (size_t i = 0; i < Medlen; i++)
    {
        if (Medcount[i] > 0)
        {
            for (size_t j = Medcount[i]; j > 0; j--)
            {
                outA[outAp] = Med[i];
                outAp++;
            }
        }
    }

    free(Med);
    free(Medcount);
    return outA;
}

C++实现

Leetcode上917.排序数组中测试通过(效率还行
JSsort_2

vector<int> sortArray(vector<int>& nums)
{
    int MAX = 0, MIN = 0;
    for (size_t i = 0; i < nums.size(); i++)
    {
        if (nums[i] > MAX)
        {
            MAX = nums[i];
        }

        if (nums[i] < MIN)
        {
            MIN = nums[i];
        }
    }

    size_t Medlen = (size_t)MAX - MIN + 1;
    vector<int> Med(Medlen, 0);
    vector<int> Medcount(Medlen, 0);

    for (size_t i = 0; i < nums.size(); i++)
    {
        Medcount[nums[i] - MIN]++;
        Med[nums[i] - MIN] = nums[i];
    }

    vector<int> outA;
    for (size_t i = 0; i < Medlen; i++)
    {
        if (Medcount[i] > 0)
        {
            for (size_t j = Medcount[i]; j > 0; j--)
            {
                outA.push_back(Med[i]);
            }
        }
    }

    return outA;
}
Last modification:April 15th, 2020 at 09:12 am