c# - 使用计数排序为负值？ (降序)

我有一个计数排序工作，它应该对x > 0进行排序，从而对我的数组进行降序排序。但是，在考虑负数时，实现的逻辑会崩溃，因为我正在进入辅助数组values中的负索引。我在考虑以某种方式使用uint，但我对此并不十分熟悉。

如何使用计数排序解决这个问题。

static void countingSort(int[] arr)
{
    int i, j, max = -1; // I think it falls apart about here
    int[] values;

    for (i = 0; i < arr.Length; i++)
        if (arr[i] > max) max = arr[i];

    values = new int[max + 1];

    //Here it reaches for a negative index when i = 2,looking for -6.
    for (i = 0; i < arr.Max(); i++)
        values[arr[i]]++;

    i = 0; j = values.Length - 1;
    while (i < arr.Length)
    {
        if (values[j] > 0)
        {
            values[j]--;
            arr[i] = j;
            i++;
        }
        else j--;
    }
}

我知道我的问题是帮助数组的索引。而且由于我不想继续创建带有负索引的数组，所以我有些困惑。

您甚至可以在c＃中执行此操作，而无需将整个类实现为Indexer？
我知道您可以在定义明确的C语言中执行此操作：


  从C99§6.5.2.1/ 2：
  下标运算符[]的定义是E1 [E2]与（*（（E1）+（E2）））相同。


我的测试数组是{ 8, 5, -6, 7, 1, 4 }

我的预期输出是{ 8, 7, 5, 4, 1, -6 }

最佳答案

在您的示例中，您已经在扫描输入数组以查找最大值。缺少的是您也没有扫描输入数组以找到最小值。如果添加它，然后知道最小值，则可以偏移数组索引的范围以允许使用负数（如果仅处理正数，甚至可能减小数组的大小）。

看起来像这样：

static void Sort(int[] array)
{
    int min = int.MaxValue, max = int.MinValue;

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
        }

        if (array[i] > max)
        {
            max = array[i];
        }
    }

    int[] counts = new int[max - min + 1];

    for (int i = 0; i < array.Length; i++)
    {
        counts[array[i] - min]++;
    }

    int k = 0;

    for (int j = max; j >= min; j--)
    {
        for (int i = 0; i < counts[j - min]; i++)
        {
            array[k++] = j;
        }
    }
}

注意，这种排序的一个显着缺点是需要维护一个连续数组，该数组包含输入中所有可能的值。即使输入数组中只有两个元素，如果它们的值分别为int.MinValue和int.MaxValue，您将需要一个16GB大的中间数组（暂时忽略您会遇到整数数学计算的麻烦）仅使用int的数组的长度）。

另一种选择是使用字典来存储计数。这样可以避免为不存在的输入值分配内存。它还碰巧允许您只扫描一次输入，而不是扫描两次（但是这样做的代价是您要处理一个数据结构，当您添加新元素时，该数据结构必须重新分配其基础存储，因此算法复杂度并没有降低多少）。

看起来像这样：

static void Sort(int[] array)
{
    int min = int.MaxValue, max = int.MinValue;

    for (int i = 0; i < array.Length; i++)
    {
    }

    Dictionary<int, int> counts = new Dictionary<int, int>();

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
        }

        if (array[i] > max)
        {
            max = array[i];
        }

        int count;

        // If the key is not present, count will get the default value for int, i.e. 0
        counts.TryGetValue(array[i], out count);
        counts[array[i]] = count + 1;
    }

    int k = 0;

    for (int j = max; j >= min; j--)
    {
        int count;

        if (counts.TryGetValue(j, out count))
        {
            for (int i = 0; i < count; i++)
            {
                array[k++] = j;
            }
        }
    }
}