c - 将具有重复值的整数数组部分排序到存储桶中的最快方法

假设我有一个大型的未排序整数数组（C / C ++），其中大部分重复一小部分值。例如，如果我从以下数组开始：

{ 0, 3, 3, 3, 0, 1, 1, 1, 3, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 2, 0, 0, 1}

我想这样结束：

{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3}

实际上，我的数组将具有数千个元素，但是它们可以具有的值范围仍然相对较小，例如十几个可能的值。

我的问题是，传统的排序算法（qsort，mergesort等）似乎有些过大，因为它们将尝试确保每个元素都处于适当的位置。但是我正在寻找一种算法，该算法只关心将元素分组为“存储桶”，并且知道一旦实现就终止。

最佳答案

好吧，基于此：


  未排序的整数数组，大多数情况下会重复一小部分值


假设列表中有一个最大值，您可以这样做：

#include <stdio.h>
#include <string.h>

int group_vals(int *arr, size_t len, int max)
{
    int count[max+1];
    memset(count, 0, sizeof count);


    for(size_t i = 0; i < len; ++i)
        count[arr[i]]++;

    size_t index = 0;
    for(size_t i = 0; i < max + 1; ++i)
    {
        for(size_t j = 0; j < count[i]; ++j)
            arr[index++] = i;
    }
}

int main(void)
{
    int arr[] = { 0, 3, 3, 3, 0, 1, 1, 1, 3, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 2, 0, 0, 1};

    for(size_t i = 0; i < sizeof arr / sizeof *arr; ++i)
        printf("%d, ", arr[i]);
    puts("");

    group_vals(arr, sizeof arr / sizeof *arr, 3);

    for(size_t i = 0; i < sizeof arr / sizeof *arr; ++i)
        printf("%d, ", arr[i]);
    puts("");

    return 0;
}

在这里，我知道3是列表的最大值。这个输出

0, 3, 3, 3, 0, 1, 1, 1, 3, 2, 2, 3, 0, 1, 1, 1, 2, 2, 2, 2, 0, 0, 1,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1,

编辑

注意：正如用户coderredoc在注释中指出的那样，此方法的局限性
是仅当原始数组仅包含正数时才有效。
改进它以处理负数不是什么大问题：

int group_vals(int *arr, size_t len, int absmax)
{
    int count[2*absmax+1];
    memset(count, 0, sizeof count);


    for(size_t i = 0; i < len; ++i)
    {
        int v = arr[i];
        size_t idx;

        if(v == 0)
            idx = absmax;
        else
            idx = absmax + v;

        count[idx]++;
    }

    size_t index = 0;
    for(size_t i = 0; i < 2*absmax + 1; ++i)
    {
        int v;
        if(i == absmax)
            v = 0;
            v = i - absmax;

        for(size_t j = 0; j < count[i]; ++j)
        {
            arr[index++] = v;
        }
    }
}

现在，该函数期望数组绝对值的最大值。

此版本打印：

-2, 0, 1, 3, 2, 3, -2, -1, -1, 3, 3,
-2, -2, -1, -1, 0, 1, 2, 3, 3, 3, 3,

PS：我没看过约翰·兹温克的答案，但我们俩都有相同的想法，这就是
C版的。

关于c - 将具有重复值的整数数组部分排序到存储桶中的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48738281/