整数列表的排序算法

Question

我有一个大约 200 个整数的列表，其值在 1 到 5 之间。

我想学习排序算法并知道在哪里应用每种算法，因为目前我对所有事情都使用冒泡排序，而我被告知这是一种糟糕的做事方式。

对于该整数排序，最快的排序算法是什么？

编辑:事实证明，因为我知道数字是 1 到 5，所以我可以使用桶排序(？)算法，如果我没有记错的话 - 我绝对可以 - 意味着对于每个整数值1，我把它放在1组中，值2我把它放在2组中等等，然后在最后连接这些组。这似乎是一种简单而有效的方法。

但是，由于这(目前)对我来说是一个学习练习，我将消除 1 - 5 的限制，并尝试实现冒泡排序和合并排序，然后比较两者，看看哪个更快。

感谢您的帮助!

Answer 1

... which I've been told is a terrible way to do things.

首先，不要把你从互联网上随机的人(甚至是我)那里听到的任何东西当作福音。

在某些条件下，冒泡排序很好，例如当数据已经大部分排序，或者项目数相对较小时(例如 200)^(a) ，或者你的语言中没有内置排序功能，并且你的截止日期很紧，缺乏性能会惹恼客户，但缺乏功能会让你被解雇:-)

这种针对冒泡排序的偏见类似于“函数只有一个退出点”和“无跳转”规则。您应该理解它们背后的原因，以便知道何时可以安全地忽略这些规则。

无论如何，回到正确的问题。对于您的具体情况，一种有效的方法是仅计算项目然后输出它们，例如:

dim count[1..5] = {0, 0, 0, 0, 0};
for each item in list:
    count[item] = count[item] + 1
for val in 1..5:
    for quant in 1..count[val]:
        output val

这是一个 O(n) 时间和 O(1) 空间解决方案，您不会为广义排序例程找到更有效的大 O - 仅在这种情况下才有可能，因为您拥有有关数据(仅限于值 1 到 5)。

如果您想检查所有不同的排序算法，Wikipedia Sorting Algorithm page是一个有用的起点，包括主要算法及其属性。

---

^(a) 顺便说一句，以下代码(使用最坏情况数据进行冒泡排序)在功能不是很强大的 IBM T60(2GHz 双核)笔记本电脑上的 CygWin 下运行时，平均完成时间为 0.157 秒(5 个样本:0.150、0.125、0.192、0.199、0.115)。

我不会用它来排序一百万个项目(每个人都知道冒泡排序的扩展性很差)，但在大多数情况下 200 个应该没问题:

#include <stdio.h>

#define COUNT 200
int main (void) {
    int i, swapped, tmp, item[COUNT];

    // Set up worst case (reverse order) data.

    for (i = 0; i < COUNT; i++)
        item[i] = 200 - i;

    // Slightly optimised bubble sort.

    swapped = 1;
    while (swapped) {
        swapped = 0;
        for (i = 1; i < COUNT; i++) {
            if (item[i-1] > item[i]) {
                tmp = item[i-1];
                item[i-1] = item[i];
                item[i] = tmp;
                swapped = 1;
            }
        }
    }

    // for (i = 0; i < COUNT; i++)
    //     printf ("%d ", item[i]);
    // putchar ('\n');

    return 0;
}