我正在对整数键数组进行排序。
stdlib.h qsort;
这很慢，现在我的函数在每次执行时花费0.6s的排序时间，而stdlib.h qsort是1.0s；它具有与std :: sort
Timsort;
我尝试过这个：https://github.com/swenson/sort和这个：http://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17;两者都显着慢于stdlib qsort
他们的快速排序和插入排序的组合到目前为止是我的数据最快的；我尝试了各种设置，并将其作为中间元素（不是3的中间值）进行枢轴旋转，并插入以28个元素子数组（默认不是8个）开始的排序，以提供最佳性能
shell sort;
本文中有一个空白的简单实现：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
我正在对整数键数组进行排序。有关数据的信息：数组是1176个元素，长键在750 000和135 000 000之间；也可能是0。有很多重复项，在...
如果您首先通过数组进行遍历以将数字分组以消除重复项，该怎么办。每个数字都可以进入哈希表，其中数字是键，而它出现的次数是值。因此，如果数字750 000在数组中出现57次，则哈希表将持有key = 750000；值= 57。然后，您可以按键对较小的哈希表进行排序，键的长度应小于100个元素。
[一种算法利用了排序的子序列。它是合并排序的一种变体，称为Natural Merge Sort。我找不到用C实现的好例子，但是从头开始实现似乎并不难。基本上是这样的：
似乎是Radix Sort或Bucket sort，因为它们可以有效地处理整数。
构建哈希表并分配一个数组。对于输入数组中的每个项目，请检查该项目是否在哈希表中。如果是，则增加其值。如果不是，则将其插入具有值1的哈希表中，并将其附加到您的数组中。
我将尝试一个带有特殊技巧的手工编码的qsort，该技巧在每个节点上存储数字及其发生的次数。再次看到它时，您将增加计数。
考虑到排序运行，一种合理的可能性是使用in-place merge将这些运行放在一起进行大型排序，直到对整个数组进行排序为止。请注意，如果函数只需要一个C接口（而不是必须用C本身编写），则可以使用C ++标准库中的std::inplace_merge，但是可以使用extern "C"链接规范来编写函数，因此可以使用从C。
坦率地说，GNU的qsort非常好而且很难被击败，但是我最近将大多数qsort调用转换为Christopher Swenson对tim_sort