首页 > 代码库 > 编程算法 - K路归并排序(k-way merge sort) 代码(C++)
编程算法 - K路归并排序(k-way merge sort) 代码(C++)
K路归并排序(k-way merge sort) 代码(C++)
本文地址: http://blog.csdn.net/caroline_wendy
K路归并排序作为经典的外部排序算法, 是程序员必须要掌握的.
知识概念参考: <数据结构>
主要思想: 在k个已排序的文件中, 选择第一个值, 采用败者树, 更新二叉树结构, 最终选择最优值.
代码仅供参考, 如最小值用(-1)代替, 最大值用(100)代替.
/* * main.cpp * * Created on: 2014年9月11日 * Author: Spike */ #include <fstream> #include <iostream> #include <vector> using namespace std; class KWayMergeSort { public: KWayMergeSort(vector<ifstream*>& vif) : m_vifs(vif), m_ofs("out.txt") { } void calculate() { /* 分别从k个输入归并段读人该段当前第一个记录的关键字到外结点 */ for(int i = 0;i < k;++i) { input(i, b[i]); } createLoserTree(); while(b[ls[0]] != MAXKEY){ /* q指示当前最小关键字所在归并段 */ int q = ls[0]; /* 将编号为q的归并段中当前(关键字为b[q].key)的记录写至输出归并段 */ cout << b[q] << " "; m_ofs << b[q] << " "; /* 从编号为q的输入归并段中读人下一个记录的关键字 */ input(q, b[q]); /* 调整败者树,选择新的最小关键字 */ adjust(q); } /* 将含最大关键字MAXKEY的记录写至输出归并段 */ cout << endl; m_ofs << endl; } private: void input (int i, int& b) { if ((*m_vifs[i]).good()) { (*(m_vifs[i])) >> b; } } /** * 已知b[0]到b[k-1]为完全二叉树ls的叶子结点,存有k个关键字,沿从叶子 * 到根的k条路径将ls调整成为败者树。 */ void createLoserTree() { b[k] = MINKEY; /* 设置ls中“败者”的初值 */ for(int i = 0; i < k; ++i){ ls[i] = k; } /* 依次从b[k-1],b[k-2],…,b[0]出发调整败者 */ for(int i = k - 1; i >= 0; --i){ adjust(i); } } void adjust(int i) { /* ls[t]是b[s]的双亲结点 */ int t = (i + k) / 2; while (t > 0) { /* s指示新的胜者 */ if (b[i] > b[ls[t]]) { int tmp = i; i = ls[t]; ls[t] = tmp; } t = t / 2; } ls[0] = i; } private: static const int k = 4; static const int MINKEY = -1; static const int MAXKEY = 100; int b[k+1]; //败者树的叶子节点 int ls[k]; //败者树的其余节点 vector<ifstream*> m_vifs; ofstream m_ofs; }; int main(void) { vector<ifstream*> vif; ifstream* ifs0 = new ifstream("f0.txt"); ifstream* ifs1 = new ifstream("f1.txt"); ifstream* ifs2 = new ifstream("f2.txt"); ifstream* ifs3 = new ifstream("f3.txt"); vif.push_back(ifs0); vif.push_back(ifs1); vif.push_back(ifs2); vif.push_back(ifs3); KWayMergeSort k(vif); k.calculate(); delete ifs0; delete ifs1; delete ifs2; delete ifs3; return 0; }
待排序文件, 最后一个是标记, 用于停止更新败者树:
f0: 5 16 49 52 78 100 f1: 7 12 25 84 91 100 f2: 29 38 57 66 71 100 f3: 9 22 47 48 59 100
输出:
5 7 9 12 16 22 25 29 38 47 48 49 52 57 59 66 71 78 84 91
编程算法 - K路归并排序(k-way merge sort) 代码(C++)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。