计数排序是原地算法且稳定的吗？

Question

正如问题所述，我想确认计数排序算法是否为原地排序算法。

维基百科将原地算法描述为：

在计算机科学中，一个原地算法（或拉丁文 in situ）是一种使用具有少量常量额外存储空间的数据结构来转换输入的算法。该输入通常在算法执行时被输出覆盖。如果算法不是原地算法，则有时称其为非原地算法或离线算法（或拉丁文 ex situ）。

稳定排序算法会保持键（即值）相等的记录之间的相对顺序。也就是说，如果有两个记录 R 和 S 具有相同的键并且在原始列表中 R 出现在 S 之前，则稳定排序算法会使 R 在排序后的列表中出现在 S 之前。

并且在计数排序页面下方的某个位置描述了：

如上所述，计数排序不是原地算法；即使忽略计数数组，它也需要单独的输入和输出数组。

如果我们将计数排序算法定义为：

countsort(){
    for i = 0 .... n  //where n is size of input array arr[]
        countArr[ arr[i] ] += 1
    //and then traverse countArr[] and rewrite arr[] with sorted values where value>0

那么，为什么这不是一种稳定且在原地排序的方法呢？

假设输入的关键数据由数字表示，卫星数据由字符表示，则对于以下数据：

arr[] = { 1a,1b,1c,2z,5c,6c,7e,8q }  // keeping in mind only keys are sorted

这个算法不会按顺序遍历1a，然后是1b，再是1c，并以此顺序重写它们吗？而且同一个数组被覆盖了，所以我们只需要根据键的类型而不是数量来获得恒定的空间。谢谢。

- hg_git

---

就编程而言，in-place算法意味着该过程可以在同一对象上操作，无需辅助存储进行计算，但这并不一定意味着原地排序是稳定的。然而，如果我记得正确（有一个实现了整个排序函数库），计数排序是稳定的。 - Nikos M.

@NikosM。我正在处理同一个对象（数组 arr[]）。虽然每种类型的排序都需要一定数量的变量。 - hg_git

你可能想完成countsort的实现，即使只是伪代码，而不是只留下注释。 - Yakk - Adam Nevraumont

Answer 1

1. 不是原地排序算法

你的countArr并没有使用O(1)的内存，它的大小需要是array_to_be_sorted中最大值加一。因为你使用了非常量的额外内存，所以即使你覆盖了原始数组，该算法也不是原地排序算法。

基本上，你违反了以下定义：

在计算机科学中，原地算法（或拉丁语in situ）是一种使用带有少量恒定额外存储空间的数据结构来转换输入的算法。

因为你的数据结构没有使用“少量恒定的额外存储空间”。

2. 稳定的排序算法

正如你所描述的，它将保持值的原始顺序。

- IVlad

---

或者范围+1？我没有将计数排序应用于大量数字的数组。由于存在不同的键，因此数据实际上应该是范围+1。假设数据仅包含1-100，这些数字可能会在1000个元素的数组中反复出现。但它仍然需要那么大的空间吗？ - hg_git

虽然我意识到我在略微偏离经典的计数排序实现，但我仍然想要一个关于^的答案。 - hg_git

维基百科的说法是不正确的。由于递归深度的原因，in-place也包括Theta(log n)。事实上，我曾经见过被称为in-place的Theta(log^k n)空间算法（其中k>1）。 - Programmer Person

@IVlad 快速排序算法通过在同一数组上操作来使用恒定的空间，那么额外的空间从哪里来？ - hg_git

@hg_git它来自必须用于实现算法的堆栈（即使您不使用递归，也必须手动分配内存以及使用它）。 - IVlad

Answer 2

问题中提到，我想确认计数排序算法是否是原地排序算法。

计数排序是一种排序算法，可以实现原地排序和非原地排序两种方式。

- 非原地排序：稳定，O(N)的空间复杂度。 - 原地排序：不稳定，O(1)的空间复杂度。

目前Counting Sort维基页面上有更多信息。对于实现细节，American Flag Sort有一些代码片段，基本上分享了相同的思路。

正如描述的那样，计数排序不是一个原地算法；即使不考虑计数数组，它也需要单独的输入和输出数组。可以修改算法，使其将项目放入已经作为输入给出的同一数组中的排序顺序中，只使用计数数组作为辅助存储；但是，修改后的原地计数排序版本不稳定。

以下内容引用自Robert Sedgewick的C语言算法第6.10章节（关于键索引计数排序），我认为非常有帮助。

如果要对大文件进行排序，辅助数组可能会出现内存分配问题。我们可以就地完成排序（避免需要辅助数组），这样可以节省空间，但代价是算法的稳定性受到影响，因此限制了算法的实用性，因为涉及大量重复键的应用程序通常还有其他相关键，其相对顺序应该得到保留。

- Song