0

我在下面有两种不同的快速排序实现。我已经验证了这些版本的快速排序中的其他版本都可以正常工作，因为它们可以对我给出的任何数组进行正确排序。如果您注意到（至少在我看来），当数组大小大于 8 时，版本 #2 与版本 #1 完全相同n。因此，我希望当我给这两个函数一个相同的数组时大小大于 8 时，它们应该平均进行大约相同数量的组件明智比较，但事实并非如此。

对于n > 8，函数都使用sort3()和partition()函数。我也在下面列出了这些，以向您展示我如何计算组件明智比较的数量。

我知道，W(n)这些快速排序实现的理论最坏情况比较数是 (n(n+2)/4)+8。因此，对于数组大小n = 500，W(n) = 62758。对于 size 数组的测试运行n = 500，版本 #1 平均进行大约 5000 次比较，这是合理的。但是，版本 #2 平均进行 80000 次比较。显然这不可能是正确的 - 版本 #2 进行的比较比理论上的要多，W(n)并且它与版本 #1 完全相同（至少在我看来）相同的算法。

您是否看到我在第 2 版中犯的错误？

版本 #1：

void Quicksort_M3(int S[], int low, int hi)
{
    if(low < hi)
    {
        if((low+1) == hi)
        {
            comparisons++;
            if(S[low] > S[hi])
                swap(S[low],S[hi]);
        }
        else
        {
            Sort3(S,low,hi);
            if((low+2)<hi)
            {
                swap(S[low+1],S[(low+hi)/2]);
                int q = partition(S, low+1, hi-1);
                Quicksort_M3(S, low, q-1);
                Quicksort_M3(S, q+1, hi);
            }
        }
    }
}

版本 #2：

void Quicksort_Insert_M3(int S[], int n, int low, int hi)
{
    if((hi-low)<=8)
        Insertionsort(S,n);
    else 
    {
        if(low < hi)
        {
            if((low+1) == hi)
            {
                comparisons++;
                if(S[low] > S[hi])
                    swap(S[low],S[hi]);
            }
            else
            {
                Sort3(S,low,hi);
                if((low+2)<hi)
                {
                    swap(S[low+1],S[(low+hi)/2]);
                    int q = partition(S, low+1, hi-1);
                    Quicksort_Insert_M3(S, n, low, q-1);
                    Quicksort_Insert_M3(S, n, q+1, hi);
                }
            }
        }
    }
}

分割：

int partition(int *S,int l, int u)
{
    int x = S[l];
    int j = l;
    for(int i=l+1; i<=u; i++)
    {
        comparisons++;
        if(S[i] < x)
        {   
            j++;
            swap(S[i],S[j]);
        }

    }
    int p = j;
    swap(S[l],S[p]);
    return p;
}

排序3：

int Sort3(int list[], int p, int r)
{
    int median = (p + r) / 2;
    comparisons++;
    if(list[p] <= list[median])
    {
        comparisons++;
        if(list[median]>list[r])
        {
            comparisons++;
            if(list[p]<list[r])
            {
                int temp = list[p];
                list[p] = list[r];
                list[r] = list[median];
                list[median] = temp;
            }
            else
            {
                exchange(list,median,r);
            }
        }
        else
            ;

    }
    else
    {
        comparisons++;
        if(list[p] > list[r])
        {
            comparisons++;
            if(list[median] < list[r])
            {
                int temp = list[p];
                list[p] = list[median];
                list[median] = list[r];
                list[r] = temp;
            }
            else
            {
                exchange(list,p,r);
            }
        }
        else
        {
            exchange(list,p,median);
        }

    }


    return list[r];
}
4

1 回答 1

5

我认为您的错误是，当您进行插入排序时，您仍在使用数组的原始大小。因此，您最终会对整个数组进行插入排序。

于 2012-11-21T08:05:51.173 回答