精华内容
下载资源
问答
  • 外排序

    千次阅读 2013-03-07 15:25:28
    外排序(External sorting)是指能够处理极大量数据的排序算法。通常来说,外排序处理的数据不能一次装入内存,只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是一种“排序-归并”的策略。在排序...
     
    

    外排序(External sorting)是指能够处理极大量数据的排序算法。通常来说,外排序处理的数据不能一次装入内存,只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段,先读入能放在内存中的数据量,将其排序输出到一个临时文件,依此进行,将待排序数据组织为多个有序的临时文件。尔后在归并段阶将这些临时文件组合为一个大的有序文件,也即排序结果。

    外排序的一个例子是外归并排序(External merge sort),它读入一些能放在内存内的数据量,在内存中排序后输出为一个顺串(即是内部数据有序的临时文件),处理完所有的数据后再进行归并。[1][2]比如,要对 900 MB 的数据进行排序,但机器上只有 100 MB 的可用内存时,外归并排序按如下方法操作:

    1. 读入 100 MB 的数据至内存中,用某种常规方式(如快速排序堆排序归并排序等方法)在内存中完成排序。
    2. 将排序完成的数据写入磁盘。
    3. 重复步骤 1 和 2 直到所有的数据都存入了不同的 100 MB 的块(临时文件)中。在这个例子中,有 900 MB 数据,单个临时文件大小为 100 MB,所以会产生 9 个临时文件。
    4. 读入每个临时文件(顺串)的前 10 MB ( = 100 MB / (9 块 + 1))的数据放入内存中的输入缓冲区,最后的 10 MB 作为输出缓冲区。(实践中,将输入缓冲适当调小,而适当增大输出缓冲区能获得更好的效果。)
    5. 执行九路归并算法,将结果输出到输出缓冲区。一旦输出缓冲区满,将缓冲区中的数据写出至目标文件,清空缓冲区。直至所有数据归并完成。

     

    归并操作的工作原理如下:

    第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置

    第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    重复步骤3直到某一指针达到序列尾

    将另一序列剩下的所有元素直接复制到合并序列尾

     

    展开全文
  • java归并外排序

    2016-06-17 20:01:30
    java归并外排序
  • 内排序和外排序

    千次阅读 2017-09-17 15:51:33
    外排序:指在排序期间全部对象太多,不能同时存放在内存中,必须根据排序过程的要求,不断在内,外存间移动的排序。 根据排序元素所在位置的不同,排序分: 内排序和外排序。 内排序:在排序过程中,所有元素调到内存...

    内排序:指在排序期间数据对象全部存放在内存的排序。
    外排序:指在排序期间全部对象太多,不能同时存放在内存中,必须根据排序过程的要求,不断在内,外存间移动的排序。
    根据排序元素所在位置的不同,排序分: 内排序和外排序。
    内排序:在排序过程中,所有元素调到内存中进行的排序,称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同,内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
    外排序:在数据量大的情况下,只能分块排序,但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

     

    深圳程序员交流群550846167

    展开全文
  • Oracle外排序研究.pdf

    2021-10-10 06:54:04
    Oracle外排序研究.pdf
  • 真31内妻大学 针算机雪院眨件工程系 第7章排序 m概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序 真31内妻大学 针算机雪院眨件工程系 概述 数据表dai:它是待排序数据对象的有限 集合 关键码key:通常数据...
  • 内排序与外排序

    千次阅读 2015-09-10 15:14:02
    外排序:指在排序期间全部对象太多,不能同时存放在内存中,必须根据排序过程的要求,不断在内,外存间移动的排序。 根据排序元素所在位置的不同,排序分: 内排序和外排序。 内排序:在排序过程中,所有元素调到...

    内排序:指在排序期间数据对象全部存放在内存的排序。
    外排序:指在排序期间全部对象太多,不能同时存放在内存中,必须根据排序过程的要求,不断在内,外存间移动的排序。
    根据排序元素所在位置的不同,排序分: 内排序和外排序。
    内排序:在排序过程中,所有元素调到内存中进行的排序,称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同,内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
    外排序:在数据量大的情况下,只能分块排序,但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

    展开全文
  • 磁盘排序(外排序

    千次阅读 2019-02-20 16:35:22
    当参加排序的数的量太大,或内存不足以存放时,需要使用外排序外排序可以使用插入排序的思想,也可以用归并排序的思想。 下面是自己实现的归并排序思想的外排序,虽然基本做到了正确排序,且对内存的占用可以控制...

    当参加排序的数的量太大,或内存不足以存放时,需要使用外排序。外排序可以使用插入排序的思想,也可以用归并排序的思想。
    下面是自己实现的归并排序思想的外排序,虽然基本做到了正确排序,且对内存的占用可以控制,但时间效率略低。

    1. 假设能用的内存为M,每条数据占内存SIZE,则可得到内存一次性能容纳的最大数据量:MAX = M/SIZW;
    2. 建立结构体FILE含有字段:当前文件名fileName、记录当前数据值currentVal、当前是第几条数据currentPos、总共有几条数据totalData;
    3. 按FILE 中的currentVal字段建立一个FILE 类型的小顶堆(或大顶堆):prorityQ;
    4. 每次读取(<=)MAX条数据,并将其进行内部排序后,以一行一条数据的格式,输出到指定路径,并新建结构体FILE file{fileName=“当前文件的输出路径”, currentVal=第一条数据的值, currentPos=0, totalData=该次读入的数据量},并将其入堆prorityQ;
    5. 以此方式读取完全部数据后,接下来是对prorityQ的操作;
    6. 弹出prorityQ中的第一个FILE结构体对象:tmpFile,将tmpFile中的currentVal以追加的方式输出到outFile中(一行一条数据),并将tmpFile中的currentPos += 1后,
    if currentPos < totalData:
    	pass;
     else: 
    	将currentVal赋值为第currentPos 条数据的值,并将该tmpFile再次入堆;
    
    1. 重复步骤6,直至prorityQ为空后,outFile中即为已排序完成的结果。

    代码示例

    GenerateRandomNumber.h文件,生成随机数序列。

    #pragma once
    #include <random>
    #include  <time.h>
    #include <fstream>
    #include <iostream>
    using namespace std;
    
    bool	GenerateRandom(int num = 100, string fileName = "")
    {
    	bool flag = fileName != "";
    	ofstream outfile;
    	try
    	{
    		if (flag)
    		{
    			outfile.open(fileName);
    			if (!outfile)
    				throw "随机数输出文件创建失败!";
    		}
    
    		srand((unsigned int)time(NULL));
    
    		while (num--)
    		{
    			uint32_t n = rand();
    			if (flag)
    				outfile << n << endl;
    			cout << n << endl;
    		}
    		outfile.close();
    	}
    	catch (const char* msg)
    	{
    		cout << msg << endl;
    		return false;
    	}
    	return true;
    }
    

    DiskSort.h磁盘排序本体了

    #pragma once
    #include <fstream>
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <queue>
    #include <cstdio>
    using namespace std;
    
    #define MemoryLimit 1000 //Byte
    
    struct File
    {
    	string filepath;
    	int currentValue;
    	int fileIndex, totalCnt, currentPos;
    	bool operator<(const File& f) const
    	{
    		return currentValue > f.currentValue;
    	}
    };
    
    void PrintFile(vector<int> num, string& path)
    {
    	ofstream out;
    	out.open(path);
    	for (auto n : num)
    		out << n << endl;
    	out.close();
    }
    
    void seek_to_line(File file, char* num_str)
    {
    	ifstream in;
    	in.open(file.filepath);
    	int line = file.currentPos;
    	++line;
    	while (line--)
    	{
    		in.getline(num_str, 100);
    	}
    	in.close();
    	return;
    }
    
    string DiskSort(string infile_path)
    {
    	int total=0, cnt = 0;
    	auto found = infile_path.find_last_of('\\');
    	string outfile_path = infile_path.substr(0, found + 1) + "sorted.txt";
    	uint32_t maxCnt = MemoryLimit / sizeof(int32_t);
    	vector<int32_t> memN(maxCnt);//存放读入内存的数据
    	vector<File> tmpfiles;
    
    	ifstream infile; ofstream outfile;
    	try
    	{
    		infile.open(infile_path);
    		if (!infile)
    			throw "输入文件打开失败!";
    		char num_str[100];
    		int num_cnt = 0, file_cnt = 0;
    		string tmpfile_path = infile_path.substr(0, found + 1) + "tmpout";
    		while (infile.getline(num_str, 100))
    		{
    			memN[num_cnt++] = stoi(num_str);
    			if (num_cnt == maxCnt)//达到内存限制
    			{
    				total += num_cnt;
    				sort(memN.begin(), memN.begin() + num_cnt);
    				string tmp = tmpfile_path + to_string(file_cnt) + ".txt";
    				PrintFile(memN, tmp);
    				tmpfiles.push_back({ tmp,0,file_cnt++,num_cnt,0 });
    				num_cnt = 0;
    			}
    		}
    		infile.close();
    		if (num_cnt > 0)
    		{
    			total += num_cnt;
    			sort(memN.begin(), memN.begin() + num_cnt);
    			string tmp = tmpfile_path + to_string(file_cnt);
    			PrintFile(memN, tmp);
    			tmpfiles.push_back({ tmp,0,file_cnt++,num_cnt,0 });
    		}
    
    		priority_queue<File> pq;
    		ofstream outfile;
    		outfile.open(outfile_path);
    		for (auto f : tmpfiles)
    		{
    			seek_to_line(f, num_str);
    			if (strcmp(num_str, "") != 0)
    			{
    				f.currentValue = stoi(num_str);
    				++f.currentPos;
    				pq.push(f);
    			}
    		}
    		int prev_value = INT_MIN;
    		bool sorted = true;
    		while (pq.size() > 0)
    		{
    			++cnt;
    			auto f = pq.top(); pq.pop();
    			sorted = prev_value <= f.currentValue;
    			prev_value = f.currentValue;
    			outfile << f.currentValue << endl;
    			cout << f.currentValue << endl;
    			if (f.currentPos == f.totalCnt)//该文件已读取完
    			{
    				remove(f.filepath.c_str());
    				continue;
    			}
    				
    			seek_to_line(f, num_str);
    			if (strcmp(num_str, "") != 0)
    			{
    				f.currentValue = stoi(num_str);
    				++f.currentPos;
    				pq.push(f);
    			}
    		}
    		outfile.close();
    		sorted = cnt == total;
    		cout << "排序完成" << endl;
    		cout << "共读取:" << total << ";" << "被排序:" << cnt << endl;
    		cout << "正确性:";
    		if (sorted) cout << "正确" << endl;
    		else cout << "错误" << endl;
    	}
    	catch (const char* msg)
    	{
    		cout << msg << endl;
    	}
    	return outfile_path;
    }
    

    main文件

    #include <iostream>
    #include <ctime>
    #include <string>
    #include "../DiskSort/GenerateRandomNumber.h"
    #include "../DiskSort/DiskSort.h"
    using namespace std;
    
    int main()
    {
    	int  cnt = 1000000;
    	string filepath = "C:\\WorkSpace\\CPP\\DiskSort\\DiskSort\\randomlist.txt";
    	if (GenerateRandom(cnt, filepath))
    	{
    		cout << "生成成功!" << endl;
    		time_t start, end;
    		start = clock();
    		DiskSort(filepath);
    		end = clock();
    		cout << (double)(end - start) / CLOCKS_PER_SEC  << "s"<< endl;
    	}
    	else
    		cout << "生成失败!" << endl;
    
    	return 0;
    }
    
    展开全文
  • 归并排序实现外排序

    千次阅读 2016-10-29 15:16:15
    外排序,对规模大的数据进行处理。 先通过data_make制造处随机数到文件名为path的文件中去。bool data_make(char *path, int num) { FILE * fw = fopen(path, "wb"); if(fw == NULL) { return false; } ...
  • Algorithm:C++语言实现之内排序、外排序相关算法(插入排序 、锦标赛排序、归并排序) 目录 一、内排序 1、插入排序 2、锦标赛排序 3、归并排序 二、外排序 1、过程 一、内排序 1、插入排序 2、...
  • 外排序(磁盘排序)之多路归并排序的简单实现外排序(磁盘排序)之多路归并排序的简单实现
  • 第11章外排序.pdf

    2021-06-14 20:35:12
    第11章外排序.pdf
  • 外排序-多路归并

    2014-08-23 17:38:46
    外排序问题的出现,主要是因为内存不够。当需要排序的数据量过多,以至于无法一次性把所有的数据都放入内存,这导致了外排序问题的出现。解决大数据量排序的方法是:先分块排序,后进行块合并。
  • 外排序(大数据文件排序)

    千次阅读 2015-11-23 15:33:44
    内排序方法的共同特点是在排序的过程中所有数据都...这种基于外部储存设备(或文件)的排序技术就是外排序。 操作系统读写磁盘所需的时间远远超过内存运算时间,基于磁盘(文件)进行的排序多使用归并排序方法。排序分
  • Oracle外排序研究

    2009-04-02 10:41:08
    Oracle外排序研究的研究最新成果,致力于ORACLE和外排序算法研究的可以看看。
  • 数据结构10外排序.ppt

    2020-10-30 01:54:34
    第十章外排序 @内容简介 10.1外存信息的存取 10.2外部排序的方法 10.3磁盘文件的归并分类 10.3.1初始归并段的生成 10.32磁盘文件的归并过程 10.33K路归并 10.3.4多路平衡归并的实现 10.3.5置换选择排序 10.36最佳...
  • * * 第12章 外 排 序 12.1 外排序概述 12.2 磁盘排序 12.3 磁带排序 本章小结 12.1 外排序概述 文件存储在外存上,因此外排序方法与各种外存设备的特征有关,外存设备大体上可分为两类,一类是顺序存取设备,例如磁带,另...
  • 数据结构外排序PPT学习教案.pptx
  • 第13章 外排序;13.1 外存的存取特性 ;13.1 外存的存取特性;13.1 外存的存取特性;13.1 外存的存取特性;13.2 磁盘排序 ;13.2 磁盘排序;13.2 磁盘排序;13.2 磁盘排序;13.2 磁盘排序;13.2 磁盘排序;13.2 磁盘排序;13.3 ...
  • 外排序 源码 vc6.0

    2011-04-14 10:28:36
    外排序 归并排序 源码 vc6.0环境 可以作为数据结构 c/c++课程的参考
  • 归并法外排序—海量数据排序

    千次阅读 2016-11-29 20:10:55
    1.外归并排序讲完了内排序,我们来了解一下,外归并排序,外归并排序一般是应对于数据量非常大的数据,这些数据放在硬盘上,无法一次性的放到内存上。所以,我们通常采用的思路对于这些数据就是...外排序是指在排序期
  • 文件和外排序: 在外存上进行排序的最通常的方法是合并排序。这种方法由两个相对独立的阶段组成:预处理和合并排序。
  • 吕鑫老师学生信息管理系统表外排序源码,申请堆空间,将内存中的链表结点POSITION存放进数组,之后对数组里的POSITION排序,打印数组,计算量小,效率高,POSITION本质上是指针,对指针数组里的指针排序比结构体数据...
  • 外排序--基于败者树的多路归并排序算法的java实现
  • 本文介绍一种在微机上进行随机数据文件EMSD外排序方法的基本思想及其实现。这是一种有效的、较为快速的和少占用存贮空间的排序方法,尤其适用于大容量数据文件的外排序
  • 外排序中分为两步:初始游程的生成和有序文件的合并 请实现算法模拟初始游程的生成 假定系统中只能对规模为p的元素进行排序 现给定m个元素 m>p 对m个元素进行处理 给出所生成的若干个有序的初始游程 要求: 1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 367,509
精华内容 147,003
关键字:

外排序