作者主頁：paper jie的博客_CSDN博客-C語言,算法詳解領(lǐng)域博主

本文作者：大家好，我是paper jie，感謝你閱讀本文，歡迎一建三連哦。

本文錄入于《算法詳解》專欄，本專欄是針對(duì)于大學(xué)生，編程小白精心打造的。筆者用重金(時(shí)間和精力)打造，將算法基礎(chǔ)知識(shí)一網(wǎng)打盡，希望可以幫到讀者們哦。

其他專欄：《系統(tǒng)解析C語言》《C語言》《C語言-語法篇》

內(nèi)容分享：本期將對(duì)八大排序中的希爾排序進(jìn)行詳細(xì)的講解，各位看官姥爺快搬好小板凳坐好叭。

? ? -------- 不要998，不要98，只要一鍵三連，三連買不了吃虧，買不了上當(dāng)

前言

上期我們介紹了選擇排序的改進(jìn)版—堆排序，具體分析了它的基本思想，代碼的實(shí)現(xiàn)和算法復(fù)雜度，這期我們將講解八大排序的最后一個(gè)—?dú)w并排序。

什么是歸并排序

百度百科中說歸并算法就是把序列遞歸劃分成為一個(gè)個(gè)短序列，以其中只有1個(gè)元素的直接序列或者只有2個(gè)元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規(guī)則進(jìn)行排序?yàn)殚L序列。歸并排序融合了分治策略，即將含有n個(gè)記錄的初始序列中的每個(gè)記錄均視為長度為1的子序列，再將這n個(gè)子序列兩兩合并得到n/2個(gè)長度為2(當(dāng)凡為奇數(shù)時(shí)會(huì)出現(xiàn)長度為l的情況)的有序子序列；將上述步驟重復(fù)操作，直至得到1個(gè)長度為n的有序長序列。需要注意的是，在進(jìn)行元素比較和交換時(shí)，若兩個(gè)元素大小相等則不必刻意交換位置，因此該算法不會(huì)破壞序列的穩(wěn)定性，即歸并排序也是穩(wěn)定的排序算法。

我自己的理解就是歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

歸并排序的實(shí)現(xiàn)

基本思想

1 把序列分成元素個(gè)數(shù)盡量相等的兩半。?
2 把兩半元素分別進(jìn)行歸并排序。
3 把兩個(gè)有序數(shù)組合并成一個(gè)。

具體代碼

#include <stdio.h>
int merge(int r[],int s[],int x1,int x2,int x3)    //自定義實(shí)現(xiàn)一次歸并樣序的函數(shù)
{
    int i,j,k;
    i=x1;    //第一部分的開始位置
    j=x2+1;  //第二部分的開始位置
    k=x1;
    while((i<=x2)&&(j<=x3))    //當(dāng)i和j都在兩個(gè)要合并的部分中時(shí)
        if(r[i]<=r[j])    //篩選兩部分中較小的元素放到數(shù)組s中
        {
            s[k] = r[i];
            i++;
            k++;
        }
        else
        {
            s[k]=r[j];
            j++;
            k++;
        }
        while(i<=x2)    //將x1?x2范圍內(nèi)未比較的數(shù)順次加到數(shù)組r中
            s[k++]=r[i++];
        while(j<=x3) //將x2+l?x3范圍內(nèi)未比較的數(shù)順次加到數(shù)組r中
            s[k++]=r[j++];
    return 0;
}
int merge_sort(int r[],int s[],int m,int n)
{
    int p;
    int t[20];
    if(m==n)
        s[m]=r[m];
    else
    {
        p=(m+n)/2;
        merge_sort(r,t,m,p);    //遞歸調(diào)用merge_soit()函數(shù)將r[m]?r[p]歸并成有序的t[m]?t[p]
        merge_sort(r,t,p+1,n);    //遞歸一調(diào)用merge_sort()函數(shù)將r[p+l]?r[n]歸并成有序的t[p+l]?t[n]
        merge(t,s,m,p,n);    //調(diào)用函數(shù)將前兩部分歸并到s[m]?s[n】*/
    }
    return 0;
}
int main()
{
    int a[11];
    int i;
    printf("請(qǐng)輸入10個(gè)數(shù)：\n");
    for(i=1;i<=10;i++)
        scanf("%d",&a[i]);    //從鍵盤中輸入10個(gè)數(shù)
    merge_sort(a,a,1,10);    //調(diào)用merge_sort()函數(shù)進(jìn)行歸并排序
    printf("排序后的順序是：\n");
    for(i=1;i<=10;i++)
        printf("%5d",a[i]);    //輸出排序后的數(shù)據(jù)
    printf("\n");
    return 0;
}

歸并排序的實(shí)現(xiàn)原理

遞歸：調(diào)用自身 分治：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。比喻10只筷子不好折，分成5和5，5還不好折，再分成2和3，還覺得不好折，再分成1和1（1和2）。像這樣將大問題分成一樣類型的小問題，在各個(gè)擊破。歸并排序?qū)崿F(xiàn)思路：把數(shù)組從中間分開（分為左，右倆部分），左邊再次從中間分開分成倆部分，右邊再次從中間分開分成倆部分，一直這樣分下去，直到不能再分。從最底層開始一直向上有序的合并。最終完成排序。

假設(shè)我們希望從小到大排序。合并的過程主要是在兩個(gè)序列的起點(diǎn)各設(shè)置一個(gè)指針。因?yàn)閮蓚€(gè)序列已經(jīng)是分別有序的了，那我們每次只需要把兩個(gè)序列中最小的元素加以比較，將其中比較小的元素加入到臨時(shí)數(shù)組，然后將該指針向后移動(dòng)，直到其中一個(gè)序列的指針走完整個(gè)序列為止。接著需要把另一個(gè)序列可能剩下的值都加到排序之后的序列的末尾。最后將臨時(shí)數(shù)組的元素值賦值回原始數(shù)組。

這里有一點(diǎn)需要考慮的是，當(dāng)兩個(gè)序列當(dāng)前指針對(duì)應(yīng)的元素相等時(shí)，應(yīng)該移動(dòng)哪一個(gè)？雖然說移動(dòng)哪一個(gè)指針都可以，但是我們一般會(huì)移動(dòng)第一個(gè)序列的指針。因?yàn)檫@樣可以保持排序的穩(wěn)定性。即保持序列中相同值在排序之后順序不變。

歸并排序的難點(diǎn)是如何合并，實(shí)際上這是比較好理解的，但是需要寫更多的代碼，因?yàn)樾枰紤]序列為空以及把臨時(shí)序列的值存回原序列的情況?？焖倥判虻碾y點(diǎn)是如何劃分，這個(gè)問題我認(rèn)為相對(duì)歸并的難點(diǎn)是比較難理解的。

另一點(diǎn)需要注意的是，快排是先劃分過程，然后遞歸。歸并是先遞歸，然后合并?？瓷先ハ喾吹牡菍?shí)際是由于兩個(gè)排序的步驟有些是不需要做任何操作的。

復(fù)雜度

空間復(fù)雜度

遞歸代碼的空間復(fù)雜度并不能像時(shí)間復(fù)雜度那樣累加。盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間，但在合并完成之后，臨時(shí)開辟的內(nèi)存空間就被釋放掉了。在任意時(shí)刻，CPU 只會(huì)有一個(gè)函數(shù)在執(zhí)行，也就只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用。臨時(shí)內(nèi)存空間最大也不會(huì)超過 n 個(gè)元素的大小，所以歸并排序的空間復(fù)雜度是 O(n)。

時(shí)間復(fù)雜度

歸并排序的遞歸樹，樹種每層元元素的個(gè)數(shù)最多是n，也就代表著每層最多進(jìn)行n次比較，而遞歸樹最多只有l(wèi)og2n層，合在一起就是nlog2n了。文章來源地址http://www.zghlxwxcb.cn/news/detail-520038.html

到了這里，關(guān)于歸并排序的具體實(shí)現(xiàn)過程的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！