使用带负值的计数排序？（降序排列）

Question

我有一个计数排序，它可以为 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# 中做到这一点而无需将整个 class 实现为索引器吗？我知道你可以在 C 中做到这一点，它定义明确：

From C99 §6.5.2.1/2: The deﬁnition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

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

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

Answer 1

看到这个。 https://en.wikipedia.org/wiki/Counting_sort.

问题出在 "values[arr[i]]++"。如果 arr[i] returns 中的值为负数，它将不起作用。

一种可能性是编写一个函数 "Hash-key(arr[i])"，它接受数组中的任何数字并将其转换为字典键值。您可以自己编写或使用库。

如果您使用的是 C#，那么 "System.Collections" 有很多类来促进字典索引。

using System;
using System.Collections;
public class SamplesArrayList  {

   public static void Main()  {

   // Creates and initializes a new ArrayList.
   ArrayList myAL = new ArrayList();
   myAL.Add("Hello");
   myAL.Add("World");

myAL.Add("!");

您的助手将加载源 "arr" 数组中的数据。希望这有帮助。

Answer 2

它实际上可以在一个非常简单的转变中完成这里是你排序更新：

    static void countingSort(int[] arr)
    {
        int i, j, max = -1; 
        int[] values;
        //get the highest absolute value to determine the size of the array 
        for (i = 0; i < arr.Length; i++)
            if (Math.Abs(arr[i]) > max) max = Math.Abs(arr[i]);
        //create double the max size array
        values = new int[max*2 + 1];

        //when reaching a value make a shift of max size            
        for (i = 0; i < arr.Length; i++)
            values[arr[i]+max]++;

        i = 0; j = values.Length - 1;
        while (i < arr.Length)
        {
            if (values[j] > 0)
            {
                values[j]--;
                //shift back when putting in the sorted array
                arr[i] = j-max;
                i++;
            }
            else j--;
        }

    }

假设您有一个 {-4,3,2} 数组，您将创建一个大小为 (4*2+1)=9 的数组，因为最高绝对值是 -4，而shift 将为 4，因此 -4 将位于索引 0 中，例如 2 将位于值数组的索引 6 中，这样可以避免问题并获得所需的结果。

Answer 3

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

看起来像这样：

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;

    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;
            }
        }
    }
}

Answer 4

求解包含负数的数组的一种方法是：

将所有负数分开放在另一个数组中，使它们成为正数（简单地取负号），对它们使用计数排序，并将它们反转并放回负号。与此同时，分别对正数进行计数排序，并将负数与正数合并。你得到了答案！

使用带负值的计数排序？（降序排列）

Using Counting Sort with Negative values? (Descending Order)

c#

sorting

counting-sort

myAL.Add("!");

使用带负值的计数排序？ （降序排列）

Using Counting Sort with Negative values? (Descending Order)

c#

sorting

counting-sort

myAL.Add("!");

使用带负值的计数排序？（降序排列）