除了快速排序/归并排序以外，对于500个数字，最快的简单排序算法是什么？

Question

我想实现一些排序算法，使其足够快速地对500个数字进行多次排序（例如，每次将500个数字排序300次）。

我不喜欢快速排序、归并排序，因为它们比冒泡排序、选择排序、插入排序等难以实现。

只是想知道，在这种情况下，什么是最好的（简单实现且最好情况下复杂度小于O(N²)，如果有许多数字已经排过序，那就更好了）最简单的排序算法。

需要排序的数字是双精度类型。

- justyy

---

可能计数排序或桶排序的派生算法适合您的需求，因为您只需要对数字进行排序。如果您想要更高级的排序算法，甚至可以使用基数排序 ;) - Alejandro

当涉及到排序算法时，您需要指定“最佳”的含义。如果您的意思是高效，则没有既最高效又最简单的算法。 - Guffa

没有复杂度为O(2)的算法，因为那将是O(1)，也不可能有比O(1)更低的排序算法。你是指O(n²)吗？ - Guffa

是的，我的错误，我的意思是，如果许多数字已经排序，那么复杂度有时会小于O(n^2)。 - justyy

你在用哪种编程语言？很可能它的库中已经内置了一个很好的排序算法。 - Abhishek Bansal

Answer 1

我曾经比较了一些排序算法。 我发现梳排序和堆排序非常容易实现且效果很好。

void comb_sort(double *a, int size) {
    int gap = size;
    bool swapped = false;
     while ((gap > 1) || swapped) {
        if (gap > 1) gap = int(gap/1.247330950103979);
        swapped = false;
        for (int i = 0; gap + i < size; i++)
        if (a[i + gap] < a[i]) {
           swap(&a[i + gap], &a[i]);
           swapped = true;
        }
    }
}

你可以对数据集进行多种算法的分析，并选择最适合你需求的算法。 编辑：为梳排序添加我使用的魔数的计算。我在几年前的某本书中发现了这个方法（但我已经不记得是哪本书了）。

- Mohit Jain

---

@j_random_hacker 我不记得完整的证明/计算（今天翻看了我的书，但找不到我读过这个的地方）。我只记录了最终结果/数字，最适合梳排序，这个数字是1/(1-pow(e, -1 * 黄金分割)，这是我用的魔数。我使用这个因子进行了一些分析，并发现它很有效。我很久以前学习了它，并在我的代码示例中记录下来。如果我能找到它，我会在这里发布。OP正在寻找最佳情况复杂度，这是线性的。最坏情况是二次的。 - Mohit Jain

Answer 2

您可以使用基数排序，其时间复杂度为O(kn)，其中k是数据大小与输入大小相对于O(n^k)的常数边界。虽然通常使用整数进行此排序，但稍作修改即可用于双精度浮点数，如在此stackoverflow帖子中提到的那样：

Radix sort for doubles

- Alejandro