Simo Sort：低方差元素的排序算法

引言

我正在撰写一篇关于确定最快排序算法的文章，在写作过程中，我受到了许多排序算法的影响，并设计了一种新的排序算法。我将其命名为 Simo，因为这是我心中一个非常特别的人的名字：)

工作原理

它是一种递归排序算法，重复以下步骤：

1. 获取数组中数字的平均值
2. 将数组分成两个数组（数组 1 和数组 2），并将平均值选为枢轴。
3. 任何小于枢轴的值都将位于第一个数组中，任何大于枢轴的值都将位于第二个数组中。
4. 重复数组 1 和数组 2 上的相同算法，直到达到结束条件

为了优化性能

1. 结束条件不是递归函数的常规结束条件，而是使用一些我通过尝试和错误设计出的条件，这些条件大大提高了性能。
2. 如果数组大小小于 15，则使用插入排序以减少开销，1996 年的经验研究表明 15 是最佳截断值。

算法

算法的工作原理如下：

low 是第一个元素的索引，high 是最后一个元素的索引。

template <class T>
void simoSort(T a[],int low,int high)
{
    //Optimization Condition
    if(high-low>15)
    {
        double average=0;    
        int n = (high - low + 1);
        
        for (int i = low; i <= high; i++)    
            average+=a[i];

        average/=n;
        int k=low;

        for(int i = low;i<=high; i++)
        if(a[i]<average)
        {
            int tempValue = a[i];
            a[i] = a[k];
            a[k] = tempValue;

            k++;
        }

        //Optimized Stop Condition
        if(low<k-1 && k-1!=high)
            simoSort(a,low,k-1);

        if(high>k && low!=k)
            simoSort(a,k,high);
    }
    else
    {
        //Insertion Sort to reduce Overhead when recursion is not deep enough
        for (int i = low + 1; i <= high; i++) {
            int value = a[i];
            int j;
            for (j = i - 1; j >= low && a[j] > value; j--) {
              a[j + 1] = a[j];
            }
            a[j + 1] = value;
        }
    }
}

示例

“示例 1”显示了算法在正常情况下的工作方式。

“示例 2”显示了算法在最佳情况下的工作方式，即数组元素之间的方差很小。在只有两个数字“1”和“0”的情况下，该算法的复杂度为 O(n)

注意：当图示中的算法停止时，表示一个叶子节点已经达到了结束条件。

复杂性

该搜索是稳定的，并且具有 O(1) 的上限空间复杂度

在完成时间复杂度分析计算后。

• 平均和最坏情况下的复杂度为 (5/6)*nlogn，映射为 O(nlogn)
• 最佳情况为 O(n)，如示例 2 所示。

如果有人能够证明这些值是错误的，请告诉我，我将进行修改，谢谢。

根据我制作的基准测试，当元素的方差较低（不超过 5 个不同的元素）时，该算法目前比快速排序和桶排序更快，并且我目前正在撰写一篇文章，将比较所有排序算法，包括这个算法。 

限制

该算法的当前版本仅适用于整数。它不适用于字符或双精度值。

历史

1.0 (2012 年 3 月 10 日)

• 初始发布。

我希望这篇文章至少能稍微帮助那些对这个问题感兴趣的人。欢迎告诉我任何关于该算法的意见：)