合併排序

合併排序

  1. 演算法思想

對於輸入的數組a[i , j],將其分為大致相同的2個子集，利用遞歸一直分下去，然後分別對2個子集進行排序（在合併中體現），最終完成排序。

  2. 演算法實現

template<class T>
void Copy(T a[], T b[], int left, int right)
{
    for(int i = left; i <= right; i++){
        a[i] = b[i];
    }
} 

template<class T>
void Merge(T a[], T b[], int left, int middle, int right)
{
    int r = middle + 1, k = left;
    while( (left <= middle) && (r <= right) ){
        if(a[left] <= a[r])  b[k++] = a[left++];
        else b[k++] = a[r++];
    }
    while(left <= middle) b[k++] = a[left++];
    while(r <= right) b[k++] = a[r++];
}

template<class T>
void MergeSort(T a[], T b[], int left, int right)
{
    if(left < right){
        int temp = ( (left + right) / 2);
        MergeSort(a,b,left, temp);
        MergeSort(a,b,temp + 1,right);
        Merge(a,b,left,temp,right);
        Copy(a,b,left,right); 
    }
}

3. 演算法分析

在Merge排序中，其時間複雜度與輸入數組是否有序無關，最壞時間複雜度和平均時間複雜度均為Ο(nlog(n))，其空間複雜度為Ο(n)，體現在輔助數組。