二路归并排序C++达成

发布时间：2021-11-20 13:04:51 所属栏目：PHP教程来源：互联网

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

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

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

#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;
}

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php读取大文件最好的实	php无限遍历文件夹示例
php中实现过滤UBB代码	Laravel模板引擎Blade