如何简单验证计数排序（counting sort）稳定性？

Question

如题

Answer 1

计数排序可以分解为如下几步：

遍历数组
记录当前遍历项
顺序输出计数器中的非空项

从中可以看出，对于数组中相等的项，在数组中 index 较小的，会先进入计数器的记录中，所以如果需要稳定性，则只需要计数器采用FIFO的设计模式（Queue）即可。

如输入项为

struct DataPack {
  int intVal;
  char data;
};
DataPack data[3] = {{0, 'a'}, {1, 'b'}, {0, 'c'}};

按照第一项int进行排序，使用计数器为

vector< queue< DataPack *> > counter(INT_MAX);

遍历代码也很简单

for (int i = 0; i < 3; ++i) {
  counter[data[i].intVal].push(&data[i]);
}

输出代码

for (int i = 0; i < INT_MAX; ++i) {
  while (counter[i].empty() == false) {
   cout << counter[i].front().intVal << ":" << counter[i].front().data << endl;
   counter[i].pop();
  }
}