-
2021-12-16 11:06:15
外排序 就是比如说你在文件中你有很大的数组 你无法一起加载到内存中 只能一部分一部分的加载带内存中,然后对它进行排序,他的思想就是 我先分为几份,然后对每一份先排序,排完序后我再进行归并排序,具体步骤程序都标注明白了 。请看程序注释就可以 拿过来直接就可以跑
另外 快速排序在这里就不给了 上一篇已经给了
void _mergefile(const char* file1, const char* file2, const char* mergefile) { FILE* fout1 = fopen(file1, "r"); if (fout1 == NULL) { printf("文件打开失败\n"); exit(-1); } FILE* fout2 = fopen(file2, "r"); if (fout2 == NULL) { printf("文件打开失败\n"); exit(-1); } FILE* fin = fopen(mergefile, "w"); if (fin == NULL) { printf("文件打开失败\n"); exit(-1); } //读取1 2 文件的数据 然后进行归并排序把他们放入到merfefile文件中 int num1, num2; int ret1 = fscanf(fout1, "%d\n", &num1); int ret2 = fscanf(fout2, "%d\n", &num2); while (ret1 != EOF && ret2 != EOF) { if (num1 < num2) { fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d\n", &num1); } else { fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d\n", &num2); } } while (ret1 != EOF) { fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d\n", &num1); } while (ret2 != EOF) { fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d\n", &num2); } fclose(fout1); fclose(fout2); fclose(fin); } void mergesortfile(const char* file) { FILE* fout = fopen(file, "r"); if (file == NULL) { printf("文件打开失败\n"); exit(-1); } //打开文件后要读取里面的数据 int num = 0; int a[10];//把整个文件平分 使每一个小文件先承载10个数据 int i = 0; int n = 10; char subfile[20]; int filei = 1; while (fscanf(fout, "%d\n", &num)!=EOF) { if (i < n - 1) { a[i] = num; i++; } else { a[i] = num; //之前读了9个 现在再加上一个 为10个 不能在上面<n这样会丢失一个数据 //接着对读到的这10个数据先进行快速排序处理 Quicksort(a, 0, n - 1); //快速排序完要创建一个子文件夹用来保存已经拍好的数组a中的10 个数据 sprintf(subfile, "%d", filei++); //接着打开这个subfile文件 FILE* fin = fopen(subfile, "w"); //文件打开后将数组中的数据写入文件 for (int j = 0;j < n; j++) { fprintf(fin, "%d\n", a[j]); } //数据写完后 关闭 文件 fclose(fin); i = 0; } } //接着用归并排序, 将之前写好的文件一一排序; char mergefile[100] = "12"; char file1[100] = "1"; char file2[100]; //应该从第二个文件开始 到第n个文件 依次与之前的文件两两归并 for (int i = 2; i <= n; i++) { sprintf(file2, "%d", i); _mergefile(file1, file2, mergefile); strcpy(file1, mergefile); //将mergefile里面的内容拷贝到file1中 sprintf(mergefile, "%s%d", mergefile, i++); } fclose(fout); } int main() { //srand((unsigned int )time(NULL)); /*insertsort(); shellsort(); heapsort(); bubble_sort(); quicksort();*/ //Mergesort(); //char* file; mergesortfile("file.txt"); system("pause"); return 0; }
更多相关内容 -
外排序(归并排序算法)
2020-06-22 19:39:30外排序,当然在我看来,外排序考验的是一个程序员的架构能力,而不仅仅局限于排序这个层次。 一:N路归并排序 1.概序 我们知道算法中有一种叫做分治思想,一个大问题我们可以采取分而治之,各个突破,当子问题...本文转自https://www.cnblogs.com/huangxincheng/archive/2012/12/19/2824943.html
说到排序,大家第一反应基本上是内排序,是的,算法嘛,玩的就是内存,然而内存是有限制的,总有装不下的那一天,此时就可以来玩玩
外排序,当然在我看来,外排序考验的是一个程序员的架构能力,而不仅仅局限于排序这个层次。
一:N路归并排序
1.概序
我们知道算法中有一种叫做分治思想,一个大问题我们可以采取分而治之,各个突破,当子问题解决了,大问题也就KO了,还有一点我们知道
内排序的归并排序是采用二路归并的,因为分治后有LogN层,每层两路归并需要N的时候,最后复杂度为NlogN,那么外排序我们可以将这个“二”
扩大到M,也就是将一个大文件分成M个小文件,每个小文件是有序的,然后对应在内存中我们开M个优先队列,每个队列从对应编号的文件中读取
TopN条记录,然后我们从M路队列中各取一个数字进入中转站队列,并将该数字打上队列编号标记,当从中转站出来的最小数字就是我们最后要排
序的数字之一,因为该数字打上了队列编号,所以方便我们通知对应的编号队列继续出数字进入中转站队列,可以看出中转站一直保存了M个记录,
当中转站中的所有数字都出队完毕,则外排序结束。如果大家有点蒙的话,我再配合一张图,相信大家就会一目了然,这考验的是我们的架构能力。
图中这里有个Batch容器,这个容器我是基于性能考虑的,当batch=n时,我们定时刷新到文件中,保证内存有足够的空间。
扩展
leveldb应用
在 LevelDB 数据库中高层数据下沉到低层时需要经历一次 Major Compaction,将高层文件的有序键值对和低层文件的多个有序键值对进行归并排序。磁盘多路归并排序算法的输入是来自多个磁盘文件的有序键值对,在内存中将这些文件的键值对进行排序,然后输出到一到多个新的磁盘文件中。
多路归并排序在大数据领域也是常用的算法,常用于海量数据排序。当数据量特别大时,这些数据无法被单个机器内存容纳,它需要被切分位多个集合分别由不同的机器进行内存排序(map 过程),然后再进行多路归并算法将来自多个不同机器的数据进行排序(reduce 过程),这是流式多路归并排序,为什么说是流式排序呢,因为数据源来源于网络套接字。
多路归并排序的优势在于内存消耗极低,它的内存占用和输入文件的数量成正比,和数据总量无关,数据总量只会线性正比影响排序的时间。
下面我们来亲自实现一下磁盘多路归并算法,为什么是磁盘,因为它的输入来自磁盘文件。
算法思路
我们需要在内存里维护一个有序数组。每个输入文件当前最小的元素作为一个元素放在数组里。数组按照元素的大小保持排序状态。
接下来我们开始进入循环,循环的逻辑总是从最小的元素下手,在其所在的文件取出下一个元素,和当前数组中的元素进行比较。根据比较结果进行不同的处理,这里我们使用二分查找算法进行快速比较。注意每个输入文件里面的元素都是有序的。
1. 如果取出来的元素和当前数组中的最小元素相等,那么就可以直接将这个元素输出。再继续下一轮循环。不可能取出比当前数组最小元素还要小的元素,因为输入文件本身也是有序的。
2. 否则就需要将元素插入到当前的数组中的指定位置,继续保持数组有序。然后将数组中当前最小的元素输出并移除。再进行下一轮循环。
3. 如果遇到文件结尾,那就无法继续调用 next() 方法了,这时可以直接将数组中的最小元素输出并移除,数组也跟着变小了。再进行下一轮循环。当数组空了,说明所有的文件都处理完了,算法就可以结束了。
值得注意的是,数组中永远不会存在同一个文件的两个元素,如此才保证了数组的长度不会超过输入文件的数量,同时它也不会把没有结尾的文件挤出数组导致漏排序的问题。 -
C语言实现排序算法之归并排序详解
2020-12-25 16:08:18排序算法中的归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 一、实现原理: 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的... -
归并排序
2021-01-06 08:21:28归并排序: 思路:分而治之 采用的是递归 主要是两步,先把数组分成两半(merge),再把这两半合并成有序的数组(mergeTwoSortedArrays)。 temp参数的作用是接收排序后的数组,然后再把值一一付给原数组,如果不加... -
数据结构之外部排序:归并排序法
2020-04-22 12:07:11外部排序:归并排序法外部归并排序的原理:外部归并排序的性能: 外部归并排序的原理: 第一步: 第二步: 问题:内存缓存区大小固定,外存数据元素分块后仍然无法将俩块放入比较 答:因为归并段已经块内有序,...外部排序:归并排序法
思维导图:
外部归并排序的原理:
第一步:
第二步:
问题:内存缓存区大小固定,外存数据元素分块后仍然无法将俩块放入比较
答:因为归并段已经块内有序,所以只需要将归并段部分装入内存,比较每个归并段相同位置元素的先后次序写入结果集即可
例:有俩个归并段1358和2467,每个缓存区可以存放2个数据元素
1、先将俩个个归并段的前俩个数据元素写入内存
2、然后12比较输出1,缓存区1标记后移;23比较输出2,标记后移;
3、输出缓存区满,写入外存
4、然后34比较输出3,缓存区1比较完毕清空,将后俩个数据元素放入继续比较
5、重复上述的过程直到比较结束
外部归并排序的性能:
归并段个数 * 每个归并段内部排序时间 + 磁盘IO读写的次数 * 每个归并块读写的时间 + 归并趟数 * 比较次数
3:排序成归并块的读写、俩次归并排序的读写
(4+4) : 四次读 + 四次写ps: IO读写的时间 >> 内部排序时间,所以优化外部归并排序,就要减少IO读写次数
问题: 如何减少IO读写次数?
答: 二路归并排序变四路归并排序
总时间主要是受 外存读写时间的控制,而外存读写时间受归并趟数的影响,所以,要想减少总时间,就要减少归并趟数(多路归并)
归并排序法的优化:
1、让K值增大
1、即增加归并路数(会增加关键字对比次数,即增加内部排序时间)
2、用败者树减少关键字对比次数2、让r减小
1、增大每块缓冲区容量
2、用“置换-选择排序”减少初始归并段数量 -
C++实现归并排序(MergeSort)
2020-08-19 06:55:41主要为大家详细介绍了C++实现归并排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
三路归并_C语言_三路归并排序_三路归并_
2021-10-03 04:31:20每次将待排序数组分为大致相等的三部分分别进行排序,然后再进行归并。 -
MATLAB实现插入排序、二分归并排序、归并排序.rar
2019-11-26 16:27:49MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。 -
C语言分治法实现归并排序
2020-12-31 22:11:38本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并... -
C++实现希尔、快速、堆排序、归并排序算法
2021-01-21 15:43:38C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。 -
C#排序算法之归并排序
2020-12-20 18:31:23本文实例为大家分享了C#实现归并排序具体代码,供大家参考,具体内容如下 代码: //归并排序(目标数组,子表的起始位置,子表的终止位置) private static void MergeSortFunction(int[] array, int first, int ... -
【数据结构】排序特辑:归并外排序(基础)
2021-11-29 14:29:24归并外排序的操作以及实现(C语言) 注:本章需要用到文件操作的知识,如果有问题,可以先浏览学习一下文件操作的知识:⭐️ C语言进阶 ⭐️ 文件操作超详解【 建议关注+收藏 】 外排序 背景 一般提到排序都...目录
前言
本章主要讲解:
归并外排序的操作以及实现(C语言)
注:本章需要用到文件操作的知识,如果有问题,可以先浏览学习一下文件操作的知识:⭐️ C语言进阶 ⭐️ 文件操作超详解【 建议关注+收藏 】
外排序
背景
一般提到排序都是指内排序,比如快速排序,堆排序,归并排序等。所谓内排序就是可以在内存中完成的排序,内存的访问速度大约是磁盘的25万倍,如果可以的话在内存中排序是非常快的。但对于大量数据来说,数据太大而无法全部都将数据加载到内存中,这时候就需要外排序。
概念
外排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。
归并外排序
在整体外排序中用归并的思想实现
- 排序策略
- 首先将整体大文件进行划分成多个内存能全加载的临时文件
- 再逐个对划分好的临时文件进行加载到内存,并进行内排序(可以使用高效的排序,建议快排)
- 排序好后对两两文件进行归并操作
- 具体归并细节:排升序
分别读取两两文件中的一个数据,进行比较,将小的数据输出到新的临时文件中,再对小数据的文件进行读取新的数据,以此循环直到归并完毕
- 图示过程:
- 实现代码:
//归并外排序 void Mergefile(const char* fin1, const char* fin2, const char* fmerge) { //以写入的方式创建合并后的新临时文件 FILE* fout = fopen(fmerge, "w"); if (fout == NULL) { perror("fopen fout fail\n"); exit(-1); } //以读取的方式打开合并子文件 FILE* file1 = fopen(fin1, "r"); if (file1 == NULL) { perror("fopen file1 fail\n"); exit(-1); } FILE* file2 = fopen(fin2, "r"); if (file2 == NULL) { perror("fopen file2 fail\n"); exit(-1); } //归并排序文件数据 int num1, num2; int ret1 = fscanf(file1, "%d\n", &num1);//文件成功读取,读取指针则自动往后走 int ret2 = fscanf(file2, "%d\n", &num2);//所以保存返回结果,比较数据写入后再读取文件 while (ret1 != EOF && ret2 != EOF) { if (num1 < num2) { //写入数据并读取下一个数据 fprintf(fout, "%d\n", num1); ret1 = fscanf(file1, "%d\n", &num1); } else { fprintf(fout, "%d\n", num2); ret2 = fscanf(file2, "%d\n", &num2); } } while (ret1 != EOF) { fprintf(fout, "%d\n", num1); ret1 = fscanf(file1, "%d\n", &num1); } while (ret2 != EOF) { fprintf(fout, "%d\n", num2); ret2 = fscanf(file2, "%d\n", &num2); } fclose(file1); fclose(file2); fclose(fout); } void MergeSortFile(const char* file, int N, int Num) { //以读取的方式打开数据文件 FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fail\n"); exit(-1); } //开辟额外空间来接收数据 int* arr = malloc(sizeof(int) * Num); if (arr == NULL) { perror("malloc fail\n"); exit(-1); } //把大文件划分成小文件,并排序 char subfile[100];//小文件名 int filei = 1, i=0, num; while(fscanf(fout, "%d\n", &num) != EOF) { if (i < Num - 1) { arr[i++] = num;//载入内存 } else//再入够数据进行排序,对排序好的数据输出到临时文件中 { arr[i] = num; QuickSort(arr, 0, Num-1);//排序 //排好后写入文件 sprintf(subfile, "Sortedfile%d", filei++);//创建修改小文件名 FILE* fin = fopen(subfile, "w");//以写入的方式创建小文件 if (fin == NULL)//文件开辟失败 { perror("fopen subfile fail\n"); exit(-1); } //输出到文件中 for (int j = 0; j < Num; j++) { fprintf(fin, "%d\n", arr[j]);//写入排好的数据 } fclose(fin); i = 0;//更新记录读取数据的个数变量 } } //开始进行合并数据文件 char fin1[100] = "Sortedfile1"; char fin2[100] = "Sortedfile2"; char fmerge[100] = "Sortedfile12"; for (i = 1; i < N; i++) { //归并文件 Mergefile(fin1, fin2, fmerge); //更替文件名 strcpy(fin1, fmerge); sprintf(fin2, "Sortedfile%d", i + 2); sprintf(fmerge, "%s%d", fmerge, i + 2); } fclose(fout); free(arr); }
测试
- 测试代码:
int main() { //获取随机种子 srand(time(0)); //创建待排序数据文件 char file[100] = "datafile.txt"; FILE* data = fopen(file, "w"); if (data == NULL) { perror("fopen fail\n"); exit(-1); } //将随机数写进写入文件 const n = 10, num = 5000; for (int i = 0; i < n * num; i++) { fprintf(data, "%d\n", rand()); } fclose(data); //排序 MergeSortFile(file, n, num); return 0; }
- 测试结果:
看来归并外排序实现的还是非常成功的!!
-
Java排序算法总结之归并排序
2020-09-03 17:22:44主要介绍了Java排序算法总结之归并排序,较为详细的分析了归并排序的原理与java实现技巧,需要的朋友可以参考下 -
c++归并排序详解
2021-01-20 06:33:11归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型... -
C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
2014-10-15 11:03:50C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序 -
归并排序_归并排序_
2021-10-01 14:36:17归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"... -
分治算法——归并排序
2020-12-21 23:32:59分治法——归并排序 归并排序操作过程: def mergesort(seq): #归并排序 if len(seq) <= 1: return seq mid = int(len(seq) / 2) # 将列表分成更小的两个列表 # 分别对左右两个列表进行处理,分别返回两个... -
今天会是有Offer的一天么:面试时你真的会写归并排序么
2020-12-21 09:28:21UP打算把八大排序算法中最难理解的几种整理一下,分别是归并排序、快排和堆排序。今天先介绍归并排序。 先说一下归并排序的图解 所谓的归并,是将两个或两个以上的有序文件合并成为一个新的有序文件,归并排序是把... -
外排序-多路归并
2016-08-01 21:27:55说到排序,大家第一反应基本上是内排序,是的,算法嘛,玩的就是内存,然而内存是有限制的,总有装...外排序,当然在我看来,外排序考验的是一个程序员的架构能力,而不仅仅局限于排序这个层次。 一:N路归并排序 -
[排序算法] 9. 归并排序递归与非递归实现及算法复杂度分析(分治算法、归并排序、复杂度分析)
2021-01-06 22:23:07文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能 -
C语言数据结构 链表与归并排序实例详解
2020-08-31 16:22:31主要介绍了C语言数据结构 链表与归并排序实例详解的相关资料,需要的朋友可以参考下 -
C++实现自顶向下的归并排序算法
2020-12-31 10:13:13本文实例讲述了C++实现自顶向下的归并排序算法。分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解、求解、合并。 1. 先将长度... -
C语言演示对归并排序算法的优化实现
2020-09-02 10:23:19主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(nlog n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下 -
C++实现归并排序算法
2020-12-20 18:15:53归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段... -
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现
2018-10-26 10:32:10冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助 -
快速排序归并排序简单排序算法比较
2013-07-16 13:51:06自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。 -
java归并外排序
2016-06-17 20:01:30java归并外排序 -
C++排序算法之归并排序源码
2020-06-29 17:44:22C++排序算法之归并排序源码 -
十大经典排序之:归并排序 |桶排序
2021-11-25 22:05:45十大经典排序之:选择排序 |堆排序选择排序选择排序原理算法实现例题堆排序堆排序原理算法实现例题