计数排序 - 实现的差异

Question

我听说过计数排序，并根据自己的理解编写了自己的版本。

public void my_counting_sort(int[] arr)
    {
        int range = 100;
        int[] count = new int[range];
        for (int i = 0; i < arr.Length; i++) count[arr[i]]++;
        int index = 0;
        for (int i = 0; i < count.Length; i++)
        {
            while (count[i] != 0)
            {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

上述代码运行良好。

然而，CLRS中给出的算法不同。以下是我的实现：

public int[] counting_sort(int[] arr)
    {
        int k = 100;
        int[] count = new int[k + 1];
        for (int i = 0; i < arr.Length; i++)
            count[arr[i]]++;
        for (int i = 1; i <= k; i++)
            count[i] = count[i] + count[i - 1];
        int[] b = new int[arr.Length];
        for (int i = arr.Length - 1; i >= 0; i--)
        {
            b[count[arr[i]]] = arr[i];
            count[arr[i]]--;
        }
        return b;
    }

我已经将伪代码直接翻译成了C#。但是代码无法运行，我收到了IndexOutOfRange异常。

我的问题是：

• 第二段代码有什么问题？
• 在算法方面，我的朴素实现和书中给出的实现有何不同？

- rohit89

---

你在第二版的counting_sort中使用了什么输入？该算法有一些限制，只允许特定的输入值。 - Jacob

int[] arr 包含范围在0-100之间的整数。我知道如果存在重复元素，该算法将无法工作。 - rohit89

Answer 1

你的版本存在问题，如果元素具有卫星数据，则无法工作。

CLRS版本可以工作，并且很稳定。

编辑：这里是CLRS版本在Python中的实现，它通过键对（key，value）进行排序：

def sort(a):
  B = 101
  count = [0] * B
  for (k, v) in a:
    count[k] += 1
  for i in range(1, B):
    count[i] += count[i-1]
  b = [None] * len(a)
  for i in range(len(a) - 1, -1, -1):
    (k, v) = a[i]
    count[k] -= 1
    b[count[k]] = a[i]
  return b    


>>> print sort([(3,'b'),(2,'a'),(3,'l'),(1,'s'),(1,'t'),(3,'e')])
[(1, 's'), (1, 't'), (2, 'a'), (3, 'b'), (3, 'l'), (3, 'e')]

- Sheldon L. Cooper

Answer 2

应该是这样的

b[count[arr[i]]-1] = arr[i];

我会让你去追踪为什么;-)。

我认为它们的表现没有任何区别。第二个只是将计数的相关性推出循环，以便在最终循环中简化一些。就我而言，这并不必要。你的方法同样直接，可能更易读。事实上（我不知道C#，因为我是Java程序员），我希望你可以用库数组填充来替换内部while循环；像这样：

       for (int i = 0; i < count.Length; i++)
    {
        arrayFill(arr, index, count[i], i);
        index += count[i];
    }

在Java中，该方法为java.util.Arrays.fill(...)。

- Mark Peters

Answer 3

问题在于您已经硬编码了使用的数组长度为100。数组的长度应该是m + 1，其中m是原始数组中的最大元素。这是您会考虑使用计数排序的第一个原因，如果您有关于数组元素都小于某个常数的信息，那么它将非常有效。

- a0viedo