午夜自慰影院,小14萝视频网站免费,欧美激情高清免费不卡

類型：游戲輔助大�。�599KB語言：中文評(píng)分：5.0
標(biāo)簽：

立即下載

早就想寫寫幾個(gè)排序的算法了，原來一直是直接調(diào)用庫函數(shù)sort()和qsort(),導(dǎo)致自己對(duì)它們內(nèi)部是實(shí)現(xiàn)機(jī)理有些忽視�，F(xiàn)在就把我剛剛手寫的一個(gè)歸并排序（時(shí)間復(fù)雜度是o(n*log(n))），其中我是用遞歸來實(shí)現(xiàn)的。在代碼中我還比較了手寫歸并，sort(),qsort(),的效率。

先對(duì)程序中所用的數(shù)據(jù)結(jié)構(gòu)做下聲明，方便大家理解接下來的程序：

int res[cnt];
int num1[cnt],num2[cnt],num3[cnt];

其中res是歸并時(shí)用的輔助數(shù)組，num1，num2，num3都是保存的是待排序的數(shù)，為了使程序具有可比性，所以把它們的元素賦成相同的值：

void init()
{
    for(int i=0;i<cnt;i++)
    {
        num3[i]=num1[i]=num2[i]=rand();
    }
}

再附上歸并排序的兩個(gè)主要函數(shù)代碼：

void merge(int start,int end,int tail)
{
    int i=start,j=end+1;
    int t=start;
    while(i<=end && j<=tail)
    {
        while(i<=end && num1[i]<=num1[j])
        {
            res[t++]=num1[i++];
        }
        while(j<=tail && num1[j]<num1[i])
        {
            res[t++]=num1[j++];
        }
        if(i>end && j<=tail)
        {
            while(j<=tail)
            {
                res[t++]=num1[j++];
            }
            break;
        }
        if(j>tail && i<=end)
        {
            while(i<=end)
            {
                res[t++]=num1[i++];
            }
            break;
        }
    }
    for(int i=start;i<=tail;i++)
    {
        num1[i]=res[i];
    }
}

void mergesort(int l,int r)
{
    if(l==r)
    {
        res[l]=num1[l];
        return ;
    }
    int mid=(l+r)>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    merge(l,mid,r);
    return ;
}

主函數(shù)如下：

int main()
{
    init();    
    clock_t clk1,clk2,clk3,clk4,clk5,clk6;
    clk1=clock();
    mergesort(0,cnt-1);
    clk2=clock();
    cout<<"歸并："<<(double)(clk2-clk1)/CLOCKS_PER_SEC<<endl;
    clk3=clock();
    sort(num2,num2+cnt);
    clk4=clock();
    cout<<"sort:"<<(double)(clk4-clk3)/CLOCKS_PER_SEC<<endl;
    clk5=clock();
    qsort(num3,cnt,sizeof(int),cmp);
    clk6=clock();
    cout<<"qsort:"<<(double)(clk6-clk5)/CLOCKS_PER_SEC<<endl;
    for(int i=0;i<cnt;i++)
    {
        if(num1[i]!=num2[i] || num1[i]!=num3[i])
        {
            cout<<"not equal"<<endl;
            cout<<setprecision(4)<<num1[i]<<"  "<<num2[i]<<"  "<<num3[i]<<" "<<i<<endl;
            break;
        }
    }
    system("pause");
    return 0;
}

最后的那個(gè)循環(huán)主要是為了用來判斷我手寫代碼的正確性。

最后我們來看一下比較效率的結(jié)果（這里通過改變cnt的數(shù)量級(jí)，來經(jīng)行多組對(duì)比）：

當(dāng)cnt=50000時(shí)的輸出為：

歸并：0.018
sort:0.099
qsort:0.039

當(dāng)cnt=500000時(shí)的輸出為：

歸并：0.181
sort:1.066
qsort:0.393

當(dāng)cnt=5000000時(shí)的輸出為：

歸并：1.931
sort:9.484
qsort:3.881

從以上三組數(shù)據(jù)可以看出它們之間的效率關(guān)系為：sort()<qsort()<手寫歸并，回到理論上它們?nèi)齻€(gè)的平均時(shí)間復(fù)雜度都是o（n*log(n)），可是在這里出現(xiàn)的差別還是比較大的。記得原來做ACM的時(shí)候經(jīng)常會(huì)聽到有人說sort()要比qsort()高效，但這里的結(jié)果卻與這個(gè)說法不相符。

開始我是懷疑排序元素類型的原因，不過換了double試了一下，還是同樣的結(jié)果，不過換用double有點(diǎn)換湯不換藥的感覺，大家如有有興趣的話可以用string類型試試。