无论如何都要对这类数据进行优化排序？

Question

我正在排序整数键的数组.

有关数据的信息:

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

---

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

1. stdlib.h qsort ;

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

2. 蒂姆索特 ;

   我试过这个:https://github.com/swenson/sort和这个:http://code.google.com/p/timsort/source/browse/trunk/timSort.c？specs = snn17&r = 17 ; 两者都明显慢于stdlib qsort

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

   到目前为止,他们对快速排序和插入排序的组合对我的数据来说是最快的; 我尝试了各种设置和pivot作为中间元素(不是3的中位数)和插入排序从28个元素子数组开始(默认情况下不是8)提供最佳性能

4. 贝壳排序 ;

   本文中的差距很简单:http://en.wikipedia.org/wiki/Shellsort ; 它很不错,虽然比stdlib 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个元素.

有了这个,您只需要通过数组一次,另一次通过更小的哈希表键列表.这应该避免大多数交换和比较.

Answer 2

你可以看看这个动画,我在这篇文章中看到了这个动画

我认为你的问题属于"少数独特"类别,其中3路分区快速排序和shell排序非常快.

更新:

我在sorting-algorithms.com上实现了一些基于伪代码的排序算法,并在OP给出的样本数据上运行它们.纯娱乐:

插入0.154s

壳0.031s

快速排序0.018s

基数0.017s

3路快速排序0.013s