快捷導(dǎo)航

C++ 歸并排序(merge sort)案例詳解

更新時(shí)間：2021年08月24日 14:22:25 作者：Joe_Somebody

這篇文章主要介紹了C++ 歸并排序(merge sort)案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

核心思想：“分”與“合”。

主體流程

先將一個(gè)序列分成很多個(gè)不能再分割的子序列，將各個(gè)子序列分別排序后再將子序列合并。其實(shí)就是重復(fù)兩個(gè)步驟：【1】分【2】合并。
首先是第一個(gè)小問題，怎么分?
比如說一個(gè)序列:12 ,23,1,44,233,10,9,8。我們先分成兩段：12 ,23,1,44 和 233,10,9,8，
發(fā)現(xiàn)還能再分成4段：12 ,23 和 1,44------233,10 和 9,8。
再分成8段：12--23--1--44 和233--10--9--8。
這時(shí)候開始把子序列進(jìn)行排序合并，一個(gè)元素就是有序的。所以不用排序。
合并成2個(gè)一組排序得到：12，23----1，44---10，233---8，9。
再合并成4個(gè)一組排序得到：1，12，23，44---8，9，10，233。
最后合并得到最終結(jié)果：1，8，9，10，12，23，44，233。

下面是分段的代碼，用遞歸實(shí)現(xiàn)。

void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左邊有序  
        mergesort(a, mid + 1, last, temp); //右邊有序  
        mergearray(a, first, mid, last, temp); //再將二個(gè)有序數(shù)列合并  
    }  
}

整體思路很清晰，還差一個(gè)小問題沒解決，怎么合并？
現(xiàn)在問題就變成了怎么合并兩個(gè)有序序列，思路是比較兩個(gè)有序序列的第一個(gè)元素，誰小把誰放進(jìn)最終序列的結(jié)尾，并把它從原來的隊(duì)列里面刪掉直到有個(gè)序列為空。
這時(shí)候另一個(gè)序列可能還有剩余的數(shù)據(jù)。沒關(guān)系，因?yàn)樗麄儽旧硎怯行虻?，所以我們只要按順序把他們添加到最終序列的尾部就好了。
這樣兩個(gè)有序序列就合并成一個(gè)有序序列了。
實(shí)現(xiàn)代碼：

void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
  
    while (i <= m)  
        temp[k++] = a[i++];  
  
    while (j <= n)  
        temp[k++] = a[j++];
}

整體測(cè)試代碼：

#include<iostream>  
#include<math.h>  
#include<stdlib.h>  
using namespace std;  
  
//將有二個(gè)有序數(shù)列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左邊有序  
        mergesort(a, mid + 1, last, temp); //右邊有序  
        mergearray(a, first, mid, last, temp); //再將二個(gè)有序數(shù)列合并  
    }  
}  
  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(a, 0, n - 1, p);  
    delete[] p;  //刪除p臨時(shí)數(shù)組
    return true;  
}  
  
int main()  
{  
    int i=0,temp=0;  
    int a[10]={0};  
    for(i=0;i<10;i++)  
{  
  
 a[i]=rand();  
 cout<<a[i]<<" ";  
  
}  
cout<<endl;  
MergeSort(a,10);  
for(i=0;i<10;i++) 
{  
    
    cout<<a[i]<<" ";  
  
}  
return 0;  
 }

到此這篇關(guān)于C++ 歸并排序(merge sort)案例詳解的文章就介紹到這了,更多相關(guān)C++ 歸并排序(merge sort)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: