c - 有没有办法优化这种数据的排序？

Question

我正在对整数键数组进行排序。

关于数据的信息:

• 数组长度为 1176 个元素
• key 介于 750 000 和 135 000 000 之间； 0也是可能的
• 有很多重复项，在每个数组中只有 48 到 100 个不同的键，但无法预测哪些值会超出整个范围
• 有很多长排序的子序列，大多数数组由 33 到 80 个排序的子序列组成
• 最小的元素为0； 0 的数量是可预测的，并且在非常窄的范围内，每个数组大约 150 个

---

到目前为止我尝试了什么:

1. stdlib.h qsort;

   这很慢，现在我的函数每次执行排序花费 0.6 秒，而 stdlib.h qsort 是 1.0 秒；这与 std::sort 具有相同的性能

2. Timsort;

   我试过这个:https://github.com/swenson/sort还有这个:http://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17 ;两者都比标准库 qsort 慢得多

3. http://www.ucw.cz/libucw/ ;

   他们的快速排序和插入排序的组合对我的数据来说是迄今为止最快的；我尝试了各种设置，将枢轴作为中间元素(不是 3 的中位数)并以 28 个元素子数组(默认情况下不是 8)开始插入排序提供了最佳性能

4. 壳排序;

   简单的实现与本文的差距:http://en.wikipedia.org/wiki/Shellsort ;它很不错，虽然比标准库 qsort 慢

---

我的想法是 qsort 做了很多交换和破坏(即反向)排序的子序列，所以应该有一些方法可以通过利用数据结构来改进它，不幸的是到目前为止我所有的尝试都失败了。
如果您想知道那是什么类型的数据，这些是在已经在之前的棋盘上排序的各种棋盘上评估的扑克牌组(这是排序的子序列的来源)。

该函数在 C 中。我使用 Visual Studio 2010。 有什么想法吗？

示例数据:http://pastebin.com/kKUdnU3N
完整执行示例(1176 种):https://dl.dropbox.com/u/86311885/out.zip

Answer 1

如果您首先通过数组对数字进行分组以去除重复项，会怎样？每个数字都可以进入哈希表，其中数字是键，它出现的次数是值。因此，如果数字 750 000 在数组中出现 57 次，哈希表将包含 key=750000；值=57。然后，您可以按键对小得多的哈希表进行排序，该哈希表的长度应少于 100 个元素。

有了这个，您只需要一次遍历数组，另一遍遍历小得多的哈希表键列表。这应该可以避免大部分交换和比较。