算法複習之兩路歸并排序

兩路歸并排序

最差時間複雜度：O(nlogn)

平均時間複雜度：O(nlogn)

最差空間複雜度：O(n)

穩定性：穩定

兩路歸并排序（Merge Sort），也就是我們常說的歸并排序，也叫合并排序。它是建立在歸并操作上的一種有效的排序算法，歸并操作即将兩個已經排序的序列合并成一個序列的操作。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

歸并操作的基本步驟如下：

1.申請兩個與已經排序序列相同大小的空間，并将兩個序列拷貝其中；

2.設定最初位置分别為兩個已經拷貝排序序列的起始位置，比較兩個序列元素的大小，依次選擇相對小的元素放到原始序列；

3.重複2直到某一拷貝序列全部放入原始序列，将另一個序列剩下的所有元素直接複制到原始序列尾。

設歸并排序的目前區間是R[low..high]，分治法的三個步驟是：

1.分解：将目前區間一分為二，即求分裂點

2.求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸并排序；

3.組合：将已排序的兩個子區間R[low..mid]和R[mid+1..high]歸并為一個有序的區間R[low..high]。

遞歸的終結條件：子區間長度為1（一個記錄自然有序）。

#include<iostream>
void prin(int *list,int len)
{
    for(int i =  ;i<len;++i)
        std::cout<<list[i]<<" ";
    std::cout<<std::endl;
}
/*
*将資料歸并
*params list:待排序的數組,low: 一個子塊的
*/
void MergeSort(int *list,int low,int mid,int high)
{
    int in1 = mid-low ; //第一路的數量
    int in2 = high-mid+ ;//第二路的數量
    int i,j,k ;
    int *left = NULL ;
    int *right = NULL ;
    left = new int[in1] ;//配置left的空間
    right = new int[in2] ;//配置right的空間
    for(i =  ;i<in1;++i) //将low---mid-1中的元素添加到left中
        left[i] = list[low+i] ;
    for(i =  ;i<in2;++i)//将mid--high中的元素添加到right中
        right[i] = list[mid+i] ;
    i = j =  ,k = low ;
    while(i<in1&&j<in2)//将兩組元素有序的合并
    {
        if(left[i] < right[j])
            list[k++] = left[i++] ;
        else
            list[k++] = right[j++] ;
    }
    for(;i<in1;i++)//剩餘left中的元素添加到數組中
        list[k++] = left[i] ;
    for(;j<in2 ;j++)//剩餘right中的元素添加到數組中
        list[k++] = right[j++] ;
    delete[] left;//回收空間
    delete[] right;//回收空間
}
/*
*歸并排序法
*list待排序的數組,low:操作元素的位置,high:待操作元素的位置
*/
void MergeSort1(int *list,int low,int high)
{
    if(low < high)
    {
        int mid = (low+high)/ ; //找分割點
        MergeSort1(list,low,mid) ;//劃分為第一路
        MergeSort1(list,mid+,high) ;//劃分為第二路
        MergeSort(list,low,mid+,high) ;//合并
    }
}
int main()
{
    int a[] = {,,,,,,,,,} ;
    MergeSort1(a,,sizeof(a)/sizeof(int)-) ;
    prin(a,) ;
    system("pause") ;
    return  ;
}