歸並排序

歸並(Merging) ：是指將兩個或兩個以上的有序序列合並成一個有序序列。若采用線性表(無論是那種存儲結構)易於實現，其時間復雜度為O(m+n)。

歸並思想實例：兩堆撲克牌，都已從小到大排好序，要將兩堆合並為一堆且要求從小到大排序。

◆ 將兩堆最上面的抽出(設為C1，C2)比較大小，將小者置於一邊作為新的一堆(不妨設C1 ◆重復上述過程，直到某一堆已抽完，然然後將剩下一堆中的所有牌轉移到新堆中。

1 排序思想

① 初始時，將每個記錄看成一個單獨的有序序列，則n個待排序記錄就是n個長度為1的有序子序列；

② 對所有有序子序列進行兩兩歸並，得到én/2ù個長度為2或1的有序子序列——一趟歸並；

③ 重復②，直到得到長度為n的有序序列為止。

上述排序過程中，子序列總是兩兩歸並，稱為2-路歸並排序。其核心是如何將相鄰的兩個子序列歸並成一個子序列。設相鄰的兩個子序列分別為：

{R[k], R[k+1], …,R[m]}和{R[m+1],R[m+2],…,R[h]}，將它們歸並為一個有序的子序列：

{DR[l],DR[l+1],…,DR[m], DR[m+1], …,DR[h] }

2.舉例

3.實現代碼：

//
//  main.cpp
//  CHelloWorld
//
//  Created by IDEA-MAC03 on 13-12-16.
//  Copyright (c) 2013年 IDEA-MAC03. All rights reserved.
//

#include 
#include 

#define SIZE 15

//完成一遍合並的函數
void MergeOne(int a[],int b[],int n,int len)
{
    int i,j,k,s,e;
    
    s = 0;
    while (s + len < n)
    {
        e = s+ 2*len -1;
        if (e >= n)
        {
            e = n-1;
        }
        //相鄰有序合並
        k = s;
        i = s;
        j = s + len;
        while (i < s+len && j<= e)
        {
            if (a[i]<= a[j])
            {
                b[k++] = a[i++];
            }
            else
            {
                b[k++] = a[j++];
            }
        }
        while (i < s+len)
        {
            b[k++] = a[i++];
        }
        
        while (j<= e)
        {
            b[k++] = a[j++];
        }
        
        s = e + 1;
    }
    if (s

運行結果：



       





參考書籍:《C/C++常用算法手冊》  《數據結構-清華大學嚴蔚敏》