计数排序是否到位且稳定？

Question

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

维基百科将就地算法描述为

在计算机科学中，就地算法（或拉丁语中的 in 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

那为什么这不是一个稳定且到位的排序呢？

假设输入由和由 字符key data表示，那么对于以下数据：numeralssatellite data

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

这个算法不会遍历 1a 然后 1b 然后 1c 并按照这个顺序重写它们吗？并且相同的数组也被覆盖，因此我们只需要一个常量空间，具体取决于键的类型而不是键的数量。

谢谢。

Answer 1

1、不到位

你countArr不占用O(1)内存，它的大小需要是max(array_to_be_sorted) + 1。由于您使用的是非常量的额外内存，因此即使您覆盖原始数组，算法也不会到位。

基本上，你打破了定义的这一部分：

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

因为您的数据结构不使用“少量、恒定的额外存储空间”。

2. 稳定

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