c++ - 为什么我的递归快速排序算法有这样不平衡的分区？

Question

我已经用 C++ 实现了一个快速排序算法。但是，我的算法运行速度比我的合并排序算法慢得多。它在反向阵列上确实运行得更快，但在其他方面它需要大约四到五倍的时间。

我的算法使用递归，但我认为这不是问题所在。我试图切换到随机枢轴而不是三个枢轴选择的中位数。那甚至更慢。

包括:

#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<iostream>

unsigned int recurse(int*a,unsigned int length)
{
    int value=0;
    unsigned int depth=0;
    if(length<=1)
    {
        depth=1;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        depth=1;
    }
    else if(length==3)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        if(a[0]>a[2])
        {
            value=a[0];
            a[0]=a[2];
            a[2]=value;
        }
        if(a[1]>a[2])
        {
            value=a[1];
            a[1]=a[2];
            a[2]=value;
        }
        depth=1;
    }
    else
    {
        //unsigned int fifth=(length>>3)+(length>>4)+(length>>6);
        unsigned int middle=length>>1;
        unsigned int choices[5]={0,middle>>1,middle,middle+(middle>>1),length-1};
        unsigned int left=0;
        unsigned int right=length-1;
        unsigned int index=0;
        for(unsigned int i=0;i<4;i++)
        {
            index=i;
            while(a[choices[index]]>a[choices[index+1]])
            {
                value=a[choices[index]];
                a[choices[index]]=a[choices[index+1]];
                a[choices[index+1]]=value;
                if(index>0)
                {
                    index--;
                }
            }
        }
        while(right>left)
        {
            while((a[++left]<=a[middle])&&right>left);
            while((a[--right]>=a[middle])&&right>left);
            if(right>left)
            {
                value=a[left];
                a[left]=a[right];
                a[right]=value;
            }
        }
        value=a[middle];
        if(left<middle&&right<middle)
        {
            a[middle]=a[left];
            a[left]=value;
            middle=left;
        }
        else if(left>middle&&right>middle)
        {
            a[middle]=a[left-1];
            a[left-1]=value;
            middle=left-1;
        }
        long double y;
        x++;
        ratio+=y=fabs((long double)(length>>1)-(long double)middle)/length;
        if(length>=1048576)
        {
            cout<<middle<<" "<<length<<" "<<y<<endl;
        }
        depth=max(recurse(a,middle),recurse(a+middle+1,length-middle-1))+1;
    }
    return depth;
}

深度只是为了计算递归深度。我想看看这是否是个问题。

int main(int argl,char**argv)
{
    unsigned int length=0;
    cin>>length;
    cout<<length<<endl;
    int*numbers=new int[length];
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    time_t start=time(0);
    mergesort(numbers,length);
    time_t end=time(0);
    cout<<end-start<<endl;
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    start=time(0);
    unsigned int depth=recurse(numbers,length);
    end=time(0);
    cout<<end-start<<endl;
    cout<<"Depth: "<<depth<<endl;
    return 0;
}

编辑:合并排序代码，按要求:

void mergesort(int*a,unsigned int length)
{
    if(length<=1)
    {
        return;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            int value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
    }
    else
    {
        unsigned int index1=0,index2=0;
        unsigned int divide1=1,divide2=1;
        unsigned int merge=2;
        unsigned int start=0;
        int*b=new int[length];
        while(merge<=length)
        {
            while(index1<divide1&&index2<divide2)
            {
                if(a[start+index1]>a[start+divide1+index2])
                {
                    b[start+index1+index2]=a[start+divide1+index2++];
                }
                else
                {
                    b[start+index1+index2]=a[start+index1++];
                }
            }
            if(index1<divide1)
            {
                for(unsigned int i=index1;index1<divide1;index1++)
                {
                    b[start+index1+index2]=a[start+index1];
                }
            }
            else
            {
                for(unsigned int i=index2;index2<divide2;index2++)
                {
                    b[start+index1+index2]=a[start+divide1+index2];
                }
            }
            if(start+merge>=length)
            {
                if(start==0)
                {
                    merge<<=1;
                }
                else
                {
                    start=0;
                    index1=0;
                    index2=0;
                    divide1=merge;
                    divide2=merge<<1>length?length-divide1:merge;
                    merge=divide1+divide2;
                }
                for(unsigned int i=0;i<length;i++)
                {
                    a[i]=b[i];
                }
            }
            else
            {
                start+=merge;
                index1=0;
                index2=0;
                divide1=start+divide1>length?length-start:divide1;
                divide2=start+merge>length?max((int)(length-(start+divide1)),0):divide2;
            }
        }
    }
}

结果，对于 33554432 个数字:编辑、更改我的代码、更新结果:

33554432
33554432
8
22
Depth: 765
0.4437349830864823

最后一个数字是轴距中心的平均距离。它几乎是 0.45，几乎是一比二十。

Answer 1

没有其他方法可以做到这一点，只能在这里回答。如果您要调用 new，请相应地调用 delete。

rand() 不是那么随机，请考虑使用 C++11 随机库。

为简洁起见，我没有包含您的算法，但我没有对其进行任何更改。我已经在 Ubuntu 和 MacOS 上运行了这段代码。

int main() {
    // Here are 50 random numbers I get when I use your method, I have put
    // them in a vector.
    std::vector<int> v = {7, 49, 89, 74, 34, 8, 24, 62, 35, 13, 24, 53,12,
                    2, 51, 71, 55, 49, 88, 52, 15, 49, 45, 5, 88, 21,
                    75, 54, 8, 7, 25, 50, 8, 19, 2, 33, 19, 13, 3, 69,
                    31, 80, 49, 72, 77, 65, 44, 43};

    // I set the size of the vector to be the size of this raw array.
    unsigned int length = v.size();

    int* numbers= new int[length];

    for(int i = 0; i < length; i++)
        numbers[i] = v[i];

    // 7 49 89 74 34 8 24 62 35 13 24 53 12 2 51 71 55...
    for (int i = 0; i < length; i++)
        std::cout << numbers[i] << " ";
    std::cout << std::endl;

    unsigned int depth = recurse(numbers, length);

    // 5 2 3 2 7 7 8 12 8 13 8 13 15 19 19 24...
    for (int i = 0; i < length; i++)
        std::cout << numbers[i] << " ";

    delete[] numbers;
    return 0;
}

我对这里发生的事情很感兴趣。也许我以某种方式弄错了，但无论哪种方式，我都希望这对(至少我们中的一个)有所帮助。

至于我的回答可能很重要的原因是，当我运行您的归并排序算法时，它会将数组中除最后一个元素之外的所有内容清零。如果确实如此，也许其他人可以证实，那么它可能比您的快速排序更有效地进行排序。

最好的，