这个排序算法的复杂度是什么？

Question

template<class T> void sSort(T *A, int first, int last) 
{
    if(A[first]>A[last])
        swap(A[first],A[last]);

    if(first+1>=last)
    return;
    double  k = floor((last-first+1)/3);


    sSort(A,first,last-k);
    sSort(A,first+k,last);
    sSort(A,first,last-k);
}

我完全理解归并排序、冒泡排序的复杂度，但是在这个算法中我很困惑。这个算法的复杂度是什么？有人能解释一下吗？

- LuckySlevin

---

你可以尝试在几个不同大小的数组上运行它，看看时间与数组大小的比较如何。 - user541686

Answer 1

这是Stooge sort。它是一个算法，旨在表明业余爱好者在没有适当分析的情况下不应该实现自己的算法。其运行时间大约为O(n^3)。

- user684934

---

谢谢，这个链接帮助我进一步查阅文档。 - LuckySlevin

Answer 2

计算并不太难。

• 每次这个算法都会对当前步骤的输入部分进行三等分，调用自身三次。 注意：第一次和第三次调用是相同的。
• 局部复杂度只是O(1)（也就是常数），因为它只会进行一次交换、一次判断和k的计算。

- Aurelio De Rosa

---

我对这种事情有点生疏，但我认为它更加复杂，因为三个递归调用在重叠的值范围上操作。 - Lars

我卡在了三个调用上，无法计算它们，我有点疯了 :) - LuckySlevin

实际上算法是可以工作的，但速度非常慢，你可以尝试运行它 : )。算法中没有任何打错字。 - LuckySlevin