桶排序:将待排序数组元素的值域拆分成多块,每块值域便是一个桶,将每个元素按照函数的映射关系,映射到一个桶中,然后分别对桶中的元素进行排序,最后合并桶中元素,完成排序

特点

当桶的个数越多即桶内元素越少,那么算法越偏向于合并桶的过程,桶排序越趋向于演化成计数排序。当桶的个数越少即桶内元素越多,那么算法越偏向于对桶内元素排序的过程,桶排序越趋向于演化成比较性排序。而决定划分为多少个桶,取决于具体的数据的值域,因此对于桶排序来说,确定待排序数据的大致组成十分重要,根据待排序数据的组成去特化(引用“模板特化”的含义)桶排序算法,使算法效率大幅度提高。

在使用桶排序时需要注意映射函数的合理性,以及注意如何处理相同的元素值

在本例中因为是在Leetcode上917.排序数组中测试因此本例是偏向于计数排序的桶排序

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率与计数排序差不多
Tsort_1

注意:该实现是返回已排序的原数组

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    int Max = nums[0], Min = nums[0];
    for (size_t i = 1; i < numsSize; i++)
    {
        if (nums[i] > Max)
        {
            Max = nums[i];
        }
        else if (nums[i] < Min)
        {
            Min = nums[i];
        }
    }

    size_t BucketSize = Max - Min + 1 + numsSize;

    int* Bucket = (int*)calloc(BucketSize, sizeof(int));
    if (!Bucket)
    {
        return nums;
    }
    memset(Bucket, 0, BucketSize * sizeof(int));

    for (size_t i = 0; i < numsSize; i++)
    {
        Bucket[nums[i] - Min]++;
    }

    for (size_t i = 0, j = 0; i < BucketSize; i++)
    {
        while (Bucket[i]--)
        {
            nums[j++] = i + Min;
        }
    }
    free(Bucket);
    return nums;
}

C++实现

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

vector<int> sortArray(vector<int>& nums)
{
    int Max = *max_element(nums.begin(), nums.end());
    int Min = *min_element(nums.begin(), nums.end());

    size_t BucketSize = Max - Min + 1 + nums.size();
    int* Bucket = new int[BucketSize] {0};

    for (size_t i = 0; i < nums.size(); i++)
    {
        Bucket[nums[i] - Min]++;
    }

    for (size_t i = 0, j = 0; i < BucketSize; i++)
    {
        while (Bucket[i]--)
        {
            nums[j++] = i + Min;
        }
    }
    delete[] Bucket;
    return nums;
}
Last modification:April 15th, 2020 at 09:11 am