对于少量整数,最快的排序算法是什么？

Question

我想知道最快的算法是什么.我有0到3000之间的8个整数,我需要对它们进行排序.虽然只有8个整数,但这个操作将执行数百万次.

Answer 1

这是C99中奇偶合并排序网络的实现(对不起"错误"语言):

#define CMP_SWAP(i, j) if (a[i] > a[j])              \
    { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

void sort8_network(int *a)
{
    CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7);
    CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7);
    CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5);
    CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5);
    CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6);
}

我在我的机器上对插入排序进行了计时

void sort8_insertion(int *a)
{
    for (int i = 1; i < 8; i++)
    {
        int tmp = a[i];
        int j = i;
        for (; j && tmp < a[j - 1]; --j)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

对于大约1000万种类别(正好是所有40320种可能的排列的250倍),排序网络花了0.39秒,而插入排序花了0.88秒.在我看来两者都足够快.(这些数字在生成排列时大约需要0.04秒.)

Answer 2

最快的是简单地编写大量if语句来比较它们以确定它们的确切顺序.这将消除任何排序算法的开销.

Answer 3

对于仅8个整数并且假设范围远大于8,插入排序可能是最好的.尝试开始,如果分析表明它不是瓶颈,那么就离开它.

(根据许多因素,快速排序变得比插入排序更好的截止点通常在5到10个项目之间).

Answer 4

最快的方法是在硬件中实现的分拣网络.除此之外,最快的方法只能通过测量来确定.我试试

• std::sort,
• 鸽笼(桶)与桶的再利用分类,
• 一堆if陈述,和
• 插入排序

按顺序,因为它是最简单到最难的顺序(尝试第一次正确插入排序......),直到你找到一些可维护的东西,一旦常数8变为值9.

此外,冒泡排序,选择值和shell排序值得注意.我从来没有真正实现过那些,因为他们有不好的代表,但你可以试试.