修改输入数组的计数排序实现

Question

在 the Wikipedia page about Counting Sort 上，它指出：

It is possible to modify the algorithm so that it places the items into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in-place version of counting sort is not stable.

我很好奇这种算法是如何实现的，但我无法访问引用的源代码。有人可以解释一下它是如何工作的吗？

Answer 1

计数后，每个值都有一个计数数组，比如：

[4,3,1,2]

右移：

[0,4,3,1]

使用累加和，将其更改为排序结果中每个值的起始位置数组：

[0,4,7,8]

现在遍历数组，将每个项目交换到其值的起始位置，并增加起始位置以便下一个进入正确的位置，但前提是该项目属于相同的或更早的位置。如果它属于后面的位置，那么就跳过它，当我们到达它时，属于那里的项目将被换入（因为它必须属于前面的位置）。

交换会将新元素带入目标位置，因此在同一位置重复，直到找到未交换的元素。

这是 JavaScript 中的算法，使用从 0 到 9 的值：

const len = 25;
const array = [];
for (let i=0; i<len; ++i) {
    array.push(Math.floor(Math.random()*10));
}
console.log("Original array:", String(array));

const cp = [0,0,0,0,0,0,0,0,0,0];
for (const val of array) {
  ++cp[val];
}
console.log("Counts:", String(cp));

for (let i=cp.length-1; i>0; --i) {
  cp[i] = cp[i-1];
}
cp[0]=0;
for (let i=1; i<cp.length; ++i) {
  cp[i]+=cp[i-1];
}
console.log("Start pointers: ", String(cp));

let pos=0;
while(pos < array.length) {
  let v = array[pos];
  let dest = cp[v];
  if (dest <= pos) {
    if (dest < pos) {
      // v belongs at an earlier position. Swap it into place
      array[pos] = array[dest];
      array[dest] = v;
    } else {
      // v belongs at the same position. don't visit it again
      ++pos;
    }
    // increment the pointer for this value
    cp[v] = dest+1;
  } else {
    // v belongs at a later position.  Something later must belong here.
    // Skip it and let the later item swap in when we get there
    ++pos;
  }
}

console.log("Sorted array:", String(array));

Answer 2

完全未经测试的 C++ 代码

#include <array>
#include <vector>
#include <algorithm>
#include <numeric>

void counting_sort(std::vector<uint8_t>& values) {
    std::array<uint8_t , 256> count;

    for(auto& value : values)
        count[value]++; // count

    std::partial_sum(count.begin(), count.end(), count.begin()); // sum

    std::array<uint8_t , 256> position;

    position[0] = 0; // first position of first value
    std::copy_n(count.begin(), count.size()-1, std::next(position.begin())); // moved by one

    int pos = 0;

    while (pos < count.size()) {
        while (count[pos] > position[pos]) {
            auto& from = position[pos]; // current position
            auto& to = position[values[from]]; // final position
            if (to != from)
              std::swap(values[from], // from current position
                        values[to]);  // where the value needs to go
            to++; // update destination position
        }
        pos++;   
    }
}

在进行交换的同时，您不断交换，直到应该放在第一个位置的值被交换到那个位置。

0 // pos
[3,2,1] // values
[0,1,1,1] // count
[_0_,1,2,3] // count
[_0_,0,1,2] // position
1 // pos
[0,_1_,2,3] // count
[0,_0_,1,2] // position

values[position[pos]] -> 3
position[3] -> 2
position[pos] -> 0
[_3_,2,_1_]
swap
[1,2,3]
position[values[pos]]++
[0,0,1,_2_] // position
[0,0,1,_3_] // position

1 // pos
[0,_1_,2,3] // count
[0,_0_,1,3] // position

values[position[pos]] -> 1
position[1] -> 0
position[pos] -> 0

positions are the same so update to
[0,_0_,1,3] // position
[0,_1_,1,3] // position

[0,_1_,2,3] // count
[0,_1_,1,3] // position
update pos
pos = 2
[0,1,_2_,3] // count
[0,1,_1_,3] // position
positions are the same to update to
[0,1,_1_,3] // position
[0,1,_2_,3] // position

count&position are the same so update pos
pos = 3
count&position are the same so update pos
pos = 4
done

修改输入数组的计数排序实现

Counting sort implementation that modifies the input array

sorting

algorithm

in-place

stable-sort

counting-sort