c – 这种排序算法的复杂性是什么？

发布时间：2020-12-16 10:20:36 所属栏目：百科来源：网络整理

导读：templateclass 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,last-k);} 我完全理解mergeS

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,last-k);
}

我完全理解mergeSort,bubbleSort的复杂性,但我在这一点上很困惑.这个算法的复杂性是多少？谁能解释一下？

解决方法

这是 Stooge sort.它是一种算法,用于表明业余爱好者在没有首先正确分析它们的情况下确实不应该实现自己的算法.它的运行时间约为O(n ^ 3).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!