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

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 等)似乎有点矫枉过正，因为它们会尽力确保每个元素都处于正确的位置。但我正在寻找一种算法，它只关心将元素分组到“桶”中，并且知道一旦实现就终止。

Answer 1

嗯，基于此:

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版本。