歸并排序 介紹

歸并排序是一種復(fù)雜度O( n l o g ( n ) nlog(n) nlog(n))的排序算法，并且在任何情況下都是，但是它不是原地算法，即需要額外存儲(chǔ)空間

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的洪洞網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

其原理是，先將區(qū)間均勻分成左右兩半，然后再對(duì)左右兩半繼續(xù)二分，直到一個(gè)數(shù)為一個(gè)區(qū)間為止。

然后從小區(qū)間到大區(qū)間進(jìn)行左右區(qū)間合并。合并方式就是將兩個(gè)有序間合并為一個(gè)大區(qū)間，并且大區(qū)間保持有序，因?yàn)樽钚^(qū)間單元是一個(gè)數(shù)，因此最初的區(qū)間一定有序，由下至上就可以保證合并過程中的區(qū)間都是有序的。

因此可以發(fā)現(xiàn)，歸并排序的核心是先遞歸后排序。

核心思想：

合并過程步驟：

• 開辟一個(gè)新的內(nèi)存空間tmp用于存放合并后的區(qū)間
• 設(shè)定兩個(gè)指針分別指向待合并的兩個(gè)區(qū)間起點(diǎn)
• 比較兩個(gè)指針的數(shù)，取較小值放入tmp
• 最后將未指向終點(diǎn)的指針?biāo)砟莻€(gè)區(qū)間接到tmp區(qū)間的后面
• 將tmp區(qū)間的內(nèi)容覆蓋回原區(qū)間

即將兩個(gè)小區(qū)間通過雙指針?biāo)惴ǎ喜橐粋€(gè)大區(qū)間，最后把大區(qū)間的內(nèi)容覆蓋回原來兩個(gè)小區(qū)間。

模板代碼：

int q[N], tmp[N];

void merge_sort(int q[N], int l, int r)
{
	if( l >= r) return;
    int mid = l + r >>1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0; // i 和 j 分別是左右區(qū)間的第一個(gè)下標(biāo)
    
    // 區(qū)間合并
    while( i<= mid && j<= r )
    {
        if( q[i]< q[j] )  tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    
    // 將剩余的區(qū)間補(bǔ)上
    while(i<= mid) tmp[k++] = q[i++];
    while(j<= r) tmp[k++] = q[j++];
    
    // 將排序好的內(nèi)容重新放回q數(shù)組
    for(int i=l, k=0; i<=r; i++, k++) q[i] = tmp[k];
}

例題

思路：

按上述模板進(jìn)行書寫即可

代碼：

#includeusing namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[N], int l, int r)
{
    if(l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l + r >>1];
    while(i< j)
    {
        do i++;while(q[i]< x);
        do j--;while(q[j] >x);
        if( i< j ) swap(q[i], q[j]);
    }
    
    quick_sort(q, l, j), quick_sort(q, j+1, r);
}

int main()
{
    scanf("%d", &n);
    for(int i=0; i

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：基礎(chǔ)算法（二）——?dú)w并排序-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://weahome.cn/article/ddhdps.html