8

通常，归并排序是通过将序列分成两半并递归排序来执行的。但是，是否也可以通过将序列除以三分之一来执行归并排序？

mergesort(array, start, last) {
tri_mid = (start+last)/3;
mergesort(array, start, tri_mid);
mergesort(array, tri_mid+1, last);
merge(array, start, last);
}

这行得通吗？如果是这样，那么 bigO 符号是什么？

4

4 回答 4

3

如果您包含第三个递归调用并正确编写合并过程，这应该可以正常工作。根据主定理，复杂度仍然是 O( n log n )。

于 2013-04-27T19:07:37.537 回答
3

是的，它肯定会起作用，但归并排序的优势在于递归的分治法。如果您每次将列表分成两半，那么您将得到 O(log2(n))，但由于计算复杂性的工作原理，这相当于 O(log n)。如果将列表拆分为不相等的两部分，那么您的大 O 表达式仍将是 O(log n)，因为您将列表在每个级别拆分为多个部分，但它可能比将列表分成两半要慢，因为算法不会以最佳状态工作，即拆分列表，对每个部分进行排序，并合并排序的子列表. 作为思考的食物，想象一下如果合并排序只选择第一个项目作为左子列表，而其他所有项目作为右子列表会发生什么。然后大 O 表达式将 O(n^2)，这与其他更糟糕的算法一样糟糕。当然，如果您想尝试一下自己的想法，那就去做，然后计时！然后你会确定什么是更快的。

于 2013-04-27T19:08:36.173 回答
1

Here you have an example of such mergesort :-)

void TRIPLE_MERGESORT(vector<double> &A, int k, int l)  
{
if(k<l)
    {
    int one_third = (l-k)/3;
    int two_third = 2*(l-k)/3;          // k < k+one_third < k+two_third < l
    TRIPLE_MERGESORT(A,k,k+one_third);
    TRIPLE_MERGESORT(A,k+one_third+1,k+two_third);
    TRIPLE_MERGESORT(A,k+two_third+1,l);
    MERGE(A,k,k+one_third,k+two_third);
    MERGE(A,k,k+two_third,l);
    }
}

Where MERGE merges arrays (vectors), which can be implemented for example as:

void MERGE(vector<double> &A, int p, int q, int r)
{
int i = p;
int j = q+1;
int lenght = r - p + 1;
int k=0;
vector<double> merged;
merged.assign (lenght,0);
while((i<=q)&&(j<=r))
    {   
    if(A[i] <= A[j])
        {
        merged[k]=A[i];
        ++i;
        }
    else
        {
        merged[k]=A[j];
        ++j;
        }
    k++;
    }

if(j<=r)
    {
    while(j<=r)
        {
        merged[k]=A[j];
        ++j;
        ++k;
        }
    }
if(i<=q)
    {
    while(i<=q)
        {
        merged[k]=A[i];
        ++i;
        ++k;
        }
    }
for (i=0;i<lenght;++i)
    A[p+i]=merged[i];
}

Have a nice day :)

//EDIT://

Cannot say exactly (but probably someone else will say it better and why it is this way), but dividing into 3 parts is more complex (and need more work) than normal mergesort, so it will take more time. It will be O(n^2) I think, but for sure worse than normal mergesort :)

于 2013-05-22T14:57:55.010 回答
1

如果将数组分成三部分，则时间复杂度的递归方程为：T(n)=3T(n/3)+O(n)。使用大师定理，时间复杂度仍为 O(nlogn)。即使您将数组划分为多个相等的部分，渐近复杂度保持不变。原因是，您必须在每次递归中做两件事，即划分和合并。合并总是需要 O(n) 时间. 因此，如果您正在考虑最小化您的时间复杂度，请尝试考虑一种可以在少于 O(n) 时间内合并两个排序数组的算法。

于 2014-10-27T02:13:06.760 回答