问最优固定大小顺序排序算法

EN

我已经研究排序算法几个星期了，但我的一个问题仍然没有答案:对于固定大小的和随机访问的集合，是否有最佳的顺序比较排序？大多数排序算法都适应于集合的大小，但是知道要排序的集合的大小可以为这个大小选择特定的排序算法。例如，下面的算法应该用最优比较数和最佳交换或赋值数(它是C++，但应该很容易翻译成任何语言)对三个值进行排序：

void sort3(int& x, int& y, int& z)
{    
    if (x < y) {
        if (z < y) {
            if (z < x) {
                int tmp = z;
                z = y;
                y = x;
                x = tmp;
            } else {
                std::swap(y, z);
            }
        }
    } else if (z < y) {
        std::swap(x, z);
    } else if (z < x) {
        int tmp = x;
        x = y;
        y = z;
        z = tmp;
    } else {
        std::swap(x, y);
    }
}

不管输入法是什么，这个算法将对三个值进行排序，最多有3个比较和4个赋值。我可能是错的，但我不认为排序三个值可以做到比这个算法更少的比较和更少的分配。如果确实如此，那么这将是对三个值进行排序的最佳比较排序算法。

由于某些排列算法，似乎可以产生任意大小的这种最优排序算法，但我找不到这样的生成算法，而且编写这样的算法似乎也不简单。我试图找到一些固定大小的近似最优排序算法，但是找不到任何简单的方法来生成这样的算法：

• 排序网络似乎是个好主意，但它们总是执行固定数量的比较和交换，这意味着它们不适应数据。即使是规模大于5qickly的最优排序网络，也会因某些输入的简单插入排序而失败。
• 并行排序算法和非比较排序(电子排序、基排序.)是有趣的，但我感兴趣的是按顺序排序小收藏。而这类算法往往隐藏了巨大的恒定复杂度，这意味着它们更适合大集合。
• 我目前寻找一个小型固定大小集合排序的最优排序算法的方法是，计算大小为N: //填充大小为N std::array集合的所有可能排列所需的比较数；std：：iota(std：：begin(集合)，std：：end(集合)，0)；插入排序cppsort::counting_adapter< cppsort::insertion_sorter >sorter进行的//计数比较；// std::size_t计数总数= 0；//对于每一个可能的集合排列，do {autoto_sort= to_sort；// +=集合，获取进行计数的+=排序器(To_sort)的数量；} uses +=std：：end( collection ))；此代码使用my cpp-排序库。我之所以使用它，是因为它可以方便地计算排序算法所做的比较，但它可以在没有排序或使用其他语言的情况下实现。但是，这种方法有一个问题:它只考虑了比较的数量，并且只能帮助找到已知算法中最优的算法，它不允许编写排序算法生成器。

这是一个很好的介绍，但我的问题基本上如下:对于固定大小的集合，是否有已知的方法来生成顺序比较排序算法，这些算法对于赋值的数量和/或所执行的比较数来说是最优的？