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

Question

假设我有一个大型未排序的整数数组 (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 等）似乎有点矫枉过正，因为它们会尽力确保每个元素都处于正确的位置。但我正在寻找一种算法，它只关心将元素分组到 "buckets" 中，并且知道一旦实现就终止。

Answer 1

使用地图：

map<int, unsigned> counts;
for (auto value: values)
    ++counts[value];

auto it = begin(values);
for (auto value_count : counts)
    while (value_count.second--)
        *it++ = value_count.first;

也就是说，创建值到计数的有序映射，然后用它覆盖（或在别处创建）每个值的正确计数的整个数组。

当然，如果值始终是小范围内的整数，您可以使用数组而不是映射——对于您的示例，值在 [0,3]:

array<unsigned, 4> counts = {};
for (auto value: values)
    ++counts[value];

Answer 2

嗯，基于此：

unsorted array of integers that mostly repeat a small range of values

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

#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: John Zwinck 的回答我没看，但是我们的想法是一样的，这是它的C版本。

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

Fastest way to partially sort array of integers with repeating values into buckets

c

arrays

sorting

algorithm

bucket