首页 > 代码库 > 数据结构：外排序-多路归并
数据结构：外排序-多路归并
外排序
外排序问题的出现，主要是因为内存不够。当需要排序的数据量过多，以至于无法一次性把所有的数据都放入内存，这导致了外排序问题的出现。解决大数据量排序的方法是：先分块排序，后进行块合并。
外排序步骤
- 把原数据分成几段读入内存，以至于每一块都可以完整的在内存中进行排序，排序好后，写入外部存储设备。
- 归并已排序好的数据块。
这就是归并排序在外排序中的应用。
对每块数据进行排序，可以使用各种内排序方法：快速排序、归并排序、堆排序等。这个比较简单，下面模拟一个对排序好的数据块进行归并的过程。
#include<iostream>
#include<iomanip>
using namespace std;
const int MAX = 100;
int key[5][5] = {
{ 3, 5, 7, MAX },
{ 1, 6, 9, MAX },
{ 2, 4, 8, MAX },
{ 0, 12, 14, MAX },
{ 10, 11, 13, 15, MAX }
};
void sort()
{
//使用pos记录每行正在参与排序的元素下标
int pos[5];
//初始化
memset(pos, 0, 5*sizeof(int));
int i, min, data;
while (true)
{
//找出第一个排序未完成的队列
i = 0;
while (i < 5 && key[i][pos[i]] == MAX)
i++;
if (i == 5) //排序完成
break;
min = i;
data = http://www.mamicode.com/key[min][pos[min]];>
运行
这是一个常见的5路归并的外排序模拟。对于每块数据的排序过程已经省略掉了，故每块数据都是有序的，我们关注的是归并的过程。在每块数据的最后加一个最大值，作为块结束的标记。
完整代码下载：外排序
专栏目录
- 数据结构与算法
- C指针
数据结构：外排序-多路归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。