二路归并排序C++实现

二路归并排序C++实现

/*
归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过"逐趟归并"使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。

二路归并排序则是归并排序中的一种最简单的情况， 它的基本操作是将两个相邻的有序子序列"归并"为一个有序序列， 如右侧所示。这个操作对顺序表而言是极其容易实现的， 只要依关键字从小到大进行"复制"即可，如下算法所示。
 */

#include <iostream>
using std::cout;
using std::endl;

void Merge(int *SR, int *TR, int i, int m, int n){
    // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
    int j = m+1;
    int k = i;
    for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中
        if (SR[i]<=SR[j]){
            TR[k] = SR[i++];
        }else{
            TR[k] = SR[j++];
        }
    }
    while (i<=m) TR[k++] = SR[i++];  // 将剩余的 SR[i..m] 复制到TR
    while (j<=n) TR[k++] = SR[j++];  // 将剩余的 SR[j..n] 复制到TR
}//Merge

void Msort( int *SR, int *TR1, int s, int t ){
    // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]
    if (s==t){
        TR1[s] = SR[s];
    }else {
        int TR2[10] ;
        int m = (s+t)/2;  // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]
        Msort(SR,TR2,s,m);  // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]
        Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
        Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]
    }// else
} // Msort

int main()
{
   
    int li[10] = {22,47,81,34,73,56,12,20,39,65};
    cout<<"注意：只整个数组R[0....9]10个元素排序"<<endl;
    for(int i = 0; i<=9; i++){
        cout << li[i] << " "; 
    }
    cout << endl;
    Msort(li,li,0,9);
    cout << endl;
    for(i = 1; i<=10; i++){
        cout << li[i-1] << " "; 
    }
    cout << endl;
    return 0;
}

本文永久更新链接地址：