C++ 败者树实现初始归并段排序算法

本文介绍了使用败者树数据结构实现初始归并段排序算法的 C++ 代码，并附带详细注释。代码展示了如何通过败者树和内存工作区，使用置换-选择排序的方法将输入文件中的记录划分为有序的初始归并段。

代码实现

#include <stdio.h>
#define MAXKEY 10000
#define RUNEND_SYMBOL 10000 // 归并段结束标志
#define w 6     // 内存工作区可容纳的记录个数
#define N 24    // 设文件中含有的记录的数量
typedef int KeyType; // 定义关键字类型为整型
// 记录类型
typedef struct {
KeyType key; // 关键字项
}RedType;
typedef int LoserTree[w];// 败者树是完全二叉树且不含叶子，可采用顺序存储结构
typedef struct
{
RedType rec; /* 记录 /
KeyType key; / 从记录中抽取的关键字 /
int rnum; / 所属归并段的段号 */
}RedNode, WorkArea[w];
// 从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段
void Select_MiniMax(LoserTree ls, WorkArea wa, int q) {
int p, s, t;
// ls[t]为q的双亲节点，p作为中介
for (t = (w + q) / 2, p = ls[t]; t &gt; 0; t = t / 2, p = ls[t]) {
    // 段号小者 或者 段号相等且关键字更小的为胜者
    if (wa[p].rnum &lt; wa[q].rnum || (wa[p].rnum == wa[q].rnum &amp;&amp; wa[p].key &lt; wa[q].key)) {
        s = q;
        q = ls[t]; //q指示新的胜利者
        ls[t] = s;
    }
}
ls[0] = q; // 最后的冠军

}
//输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录，并由s指示其在wa中的位置。
void Construct_Loser(LoserTree ls, WorkArea wa, FILE* fi) {
int i;
for (i = 0; i < w; ++i) {
wa[i].rnum = wa[i].key = ls[i] = 0;
}
for (i = w - 1; i >= 0; --i) {
fread(&wa[i].rec, sizeof(RedType), 1, fi);// 输入一个记录
wa[i].key = wa[i].rec.key; // 提取关键字
wa[i].rnum = 1; // 其段号为＂1＂
Select_MiniMax(ls, wa, i); // 调整败者树
}
}
// 求得一个初始归并段，fi为输入文件指针，fo为输出文件指针。
void get_run(LoserTree ls, WorkArea wa, int rc, int* rmax, FILE* fi, FILE* fo) {
int q;
KeyType minimax;
// 选得的MINIMAX记录属当前段时
while (wa[ls[0]].rnum == rc) {
q = ls[0];// q指示MINIMAX记录在wa中的位置
minimax = wa[q].key;
// 将刚选得的MINIMAX记录写入输出文件
fwrite(&wa[q].rec, sizeof(RedType), 1, fo);
// 如果输入文件结束，则虚设一条记录（属＂rmax+1＂段）
if (feof(fi)) {
wa[q].rnum = *rmax + 1;
wa[q].key = MAXKEY;
}
else { // 输入文件非空时
// 从输入文件读入下一记录
fread(&wa[q].rec, sizeof(RedType), 1, fi);
wa[q].key = wa[q].rec.key;// 提取关键字
if (wa[q].key < minimax) {
// 新读入的记录比上一轮的最小关键字还小，则它属下一段
*rmax = rc + 1;
wa[q].rnum = *rmax;
}
else {
// 新读入的记录大则属当前段
wa[q].rnum = rc;
}
}
// 选择新的MINIMAX记录
Select_MiniMax(ls, wa, q);
}
}
//在败者树ls和内存工作区wa上用置换－选择排序求初始归并段
void Replace_Selection(LoserTree ls, WorkArea wa, FILE* fi, FILE* fo) {
int rc, rmax;
RedType j;
j.key = RUNEND_SYMBOL;
// 初建败者树
Construct_Loser(ls, wa, fi);
rc = rmax = 1;//rc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号
while (rc &lt;= rmax) {// ＂rc=rmax+1＂标志输入文件的置换－选择排序已完成
    // 求得一个初始归并段
    get_run(ls, wa, rc, &amp;rmax, fi, fo);
    fwrite(&amp;j, sizeof(RedType), 1, fo);//将段结束标志写入输出文件
    rc = wa[ls[0]].rnum;//设置下一段的段号
}

}
void print(RedType t) {
printf("%d ", t.key);
}
int main() {
RedType a[N] = { 51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76 };
RedType b;
FILE* fi, * fo; //输入输出文件
LoserTree ls; // 败者树
WorkArea wa; // 内存工作区
int i, k;
fo = fopen_s(&fo, "ori", "wb"); //准备对 ori 文本文件进行写操作
//将数组 a 写入大文件ori
fwrite(a, sizeof(RedType), N, fo);
fclose(fo); //关闭指针 fo 表示的文件
fi = fopen_s(&fi, "ori", "rb");//准备对 ori 文本文件进行读操作
printf("文件中的待排序记录为:
");
for (i = 1; i <= N; i++) {
// 依次将文件ori的数据读入并赋值给b
fread(&b, sizeof(RedType), 1, fi);
print(b);
}
printf("
");
rewind(fi);// 使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件。
fo = fopen_s(&fo, "out", "wb");
// 用置换－选择排序求初始归并段
Replace_Selection(ls, wa, fi, fo);
fclose(fo);
fclose(fi);
fi = fopen_s(&fi, "out", "rb");
printf("初始归并段各为:
");
do {
k = fread(&b, sizeof(RedType), 1, fi); //读 fi 指针指向的文件，并将读的记录赋值给 b，整个操作成功与否的结果赋值给 k
if (k == 1) {
if (b.key == MAXKEY) {//当其值等于最大值时，表明当前初始归并段已经完成
printf("
");
continue;
}
print(b);
}
} while (k == 1);
return 0;
}

算法解释

该算法利用败者树和内存工作区来实现初始归并段的排序。败者树是一个完全二叉树，每个节点代表一个内存工作区中的记录，根节点代表当前关键字最小的记录。内存工作区用来存储从输入文件中读取的记录。

算法分为以下几个步骤：

1. 初始化败者树：将输入文件中的前 w 个记录读入内存工作区，并构建一个败者树，根节点指向内存工作区中关键字最小的记录。
2. 求得一个初始归并段：重复以下操作，直到输入文件为空：
1. 从败者树的根节点获取关键字最小的记录，并将其写入输出文件。
2. 从输入文件读取下一条记录，并将其添加到内存工作区。
3. 调整败者树，使根节点指向当前关键字最小的记录。
4. 如果新读取的记录的关键字小于当前初始归并段中的最小关键字，则创建一个新的初始归并段，并将其段号设置为 rmax + 1。
3. 将初始归并段写入输出文件：将每个初始归并段写入输出文件，并在每个初始归并段结束后写入一个段结束标志。

该算法的时间复杂度为 O(n log w)，其中 n 是输入文件中的记录数，w 是内存工作区的大小。由于 w 通常远小于 n，因此该算法的效率非常高。

应用场景

该算法可以用于实现多路归并排序，其核心思想是将输入文件分成多个有序的初始归并段，然后将这些初始归并段进行合并，最终得到一个有序的文件。

总结

本文介绍了使用败者树实现初始归并段排序算法的 C++ 代码，并对算法进行了详细解释。该算法可以用于实现多路归并排序，是归并排序算法中一个重要的步骤。