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

Question

我想实现一些排序算法，它足够快，可以对500个数字进行多次排序(例如，每次对500个数字进行300次迭代排序)

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

只是想知道什么是最好的(实现简单，在一些最好的情况下复杂度小于0 (N²)如果许多数字已经排序)最简单的排序算法在这种情况下

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

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;
        }
    }
}

你可以在你的数据集上配置多个算法，并根据你的需要选择最好的一个。

EDIT添加用于梳子排序的幻数计算。

Answer 2

您可以使用基数排序，这是O(kn)，其中k是一个常数，以O(n^k)方式将数据大小与输入大小相结合。虽然这种排序通常是对整数进行的，但稍加修改就可以将其用于双精度浮点数，正如这篇stackoverflow文章中提到的: