500个数字的最快简单排序算法(快速排序/合并排序除外)是什么？

Question

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

我不喜欢快速排序,合并排序,因为它们比冒泡排序,选择排序,插入排序更难实现.

只是想知道什么是最好的(简单的实现和一些最佳情况复杂度小于O(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;
        }
    }
}

您可以在数据集上分析多种算法，并选择最适合您需要的一种。

编辑添加我用于梳排序的幻数计算。几年前我在一本书上发现了这个（我不记得了）。