精华内容
下载资源
问答
  • 外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。
  • 外部排序

    2020-03-03 16:01:01
    外部排序 有时,待排序的文件很大,计算机内存不能容纳整个文件,这时候对文件就不能使用内部排序了(这里做一下说明,其实所有的排序都是在内存中做的,这里说的内部排序是指待排序的内容在内存中就可以完成,而...

                                              外部排序

    有时,待排序的文件很大,计算机内存不能容纳整个文件,这时候对文件就不能使用内部排序了(这里做一下说明,其实所有的排序都是在内存中做的,这里说的内部排序是指待排序的内容在内存中就可以完成,而外部排序是指待排序的内容不能在内存中一下子完成,它需要做内外存的内容交换),外部排序常采用的排序方法也是归并排序

    这种归并方法由两个不同的阶段组成

    1、采用适当的内部排序方法对输入文件的每个片段进行排序,将排好序的片段(成为归并段)写到外部存储器中(通常由一个可用的磁盘作为临时缓冲区),这样临时缓冲区中的每个归并段的内容是有序的。

    2、利用归并算法,归并第一阶段生成的归并段,直到只剩下一个归并段为止。

    例如要对外存中4500个记录进行归并,而内存大小只能容纳750个记录,在第一阶段,我们可以每次读取750个记录进行排序,这样可以分六次读取,进行排序,可以得到六个有序的归并段,如下图:

    每个归并段的大小是750个记录,记住,这些归并段已经全部写到临时缓冲区(由一个可用的磁盘充当)内了,这是第一步的排序结果。

    完成第二步该怎么做呢?这时候归并算法就有用处了,算法描述如下:

    1、将内存空间划分为三份,每份大小250个记录,其中两个用作输入缓冲区,另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并,先从每个归并段中读取250个记录到输入缓冲区,对其归并,归并结果放到输出缓冲区,当输出缓冲区满后,将其写道临时缓冲区内,如果某个输入缓冲区空了,则从相应的归并段中再读取250个记录进行继续归并,反复以上步骤,直至Segment_1和Segment_2全都排好序,形成一个大小为1500的记录,然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

    2、对归并好的大小为1500的记录进行如同步骤1一样的操作,进行继续排序,直至最后形成大小为4500的归并段,至此,排序结束。

    以上对外部排序如何使用归并算法进行排序进行了简要总结,提高外部排序需要考虑以下问题:

    1、如何减少排序所需的归并趟数。

    2、如果高效利用程序缓冲区,使得输入、输出和CPU运行尽可能地重叠。

    3、如何生成初始归并段(Segment)和如何对归并段进行归并。

     

    举个例子

       我们假设需要排序的int数有12个,内存一次只能装下3个int数。

    接下来把12个数据分成4份,然后排序成有序子串:

    然后把子串进行两两合并:

    优化策略

             因为硬盘的读写速度比内存要慢的多,按照以上这种方法,每个数据都从硬盘读了三次,写了三次,要花很多时间。

             解释下:例如对于数据2,我们把无序的12个数据分成有序的4个子串需要读写各一次,把2份3个有序子串合并成6个有序子串读写各一次;把2份6个有序子串合并从12个有序子串读写各一次,一共需要读写各3次。

             在进行有序子串合并的时候,不采取两两合并的方法,而是可以3个子串,或4个子串一起来合并。

    多路归并排序

    外部排序最常用的算法是归并排序,而多路归并排序的流程与思想也比较简单,在此不再赘言。
    但值得注意的是其重要的子算法

    1. 置换-选择排序
      n个记录分为m个规模较小的记录段,如果被划分的每个小记录段规模不够小,仍然无法完全读入内存,则无法用内排序得到初始归并段,因此需要一种适用于初始归并段规模的,高效的且不受内存空间限制的排序算法,即置换-选择排序。
    2. 最佳归并树
      将当前的m组(每组含有k个有序记录段)记录归并为m个有序记录段的过程称为一趟归并,可见每个记录在每趟归并中需要两次I/O操作(读写操作各一次)。读写操作是非常耗时的,可见减少归并次数可以提高效率。为了使得归并次数最少,需用到最佳归并树。
    3. 败者树
      归并排序算法中有一个多次出现的步骤是从当前k个值中用某种算法选出最值,可见提高选最值的效率也是整个归并排序算法效率提高的关键。这就需要用到败者树。

    置换-选择排序

    /**
    *置换-选择排序的简单描述
    */
    typedef struct{
        RcdType    rec;     //记录
        KeyType    key;    //从记录中抽取的关键字
        int    rnum;    //所属归并段的段号
    }RcdNode,  WorkArea[w];    //内存工作区,容量为w
    
    void  Replace_Selection(LoserTree  &ls,WorkArea  &wa,  FILE  *fi,  FILE  *fo){
        //  在败者树ls和内存工作区wa上用置换-选择排序求初始归并段,fi为输入文件
        //(只读文件)指针,fo为输出文件(只写文件)指针,两个文件均已打开
        Construct_Loser(ls,wa);    //初建败者树
        rc = rmax = 1;      //rc指示当前生产的初始归并段的段号
                                 //rmax指示wa中关键字所属初始归并段的最大段号
        while(rc <= rmax){    //"rc = rmax+1" 标志输入文件的置换-选择排序已完成
          get_run(ls,wa);    //求得一个初始归并段
          fwrite(&RUNEND_SYMBOL,sizeof(struct RcdType),1,fo);  //将段结束标志输入输出文件
          rc = wa[ls[0]].rnum;    //设置下一段的段号
        }
    }
    
    void get_run (LoserTree &ls,WorkArea &wa){
        //求得一个初始归并段,fi为输入文件指针,fo为输出文件指针
        while(wa[ls[0]].rnum == rc){    //选得的MINIMAX记录属当前段时
            q = ls[0];    //q知识MINIMAX记录在wa中的位置
            minimax = wa[q].key;
        }
        fwrite(&wa[q].rec,sizeof(RcdType),1,fo);    //将刚选好的MINIMAX记录写入输出文件
        if(feof(fi))    {wa[q].rnum = rmax +1; wa[q].key = MAXKEY;}
        //输入文件结束,虚设记录(属"rmax+1"段)
        //输入文件非空时
        else{
            fread(&wa[q].rec,sizeof(RcdType),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;    //新读入的记录属当前段
            }
              Select_MiniMax(ls,wa,q);    选择新的MINIMAX记录
        }
        
    void Select_MiniMax(LoserTree &ls,WorkArea wa,int q){
            //从wa[q]起到败者树的根比较选择MINIMAX记录,并由q指示它所在的归并段
            for(t = (w+q)/2,p = ls[t];t>0; t= t/2,p = ls[t]){
                if(wa[p].rnum <wa[q].rnum || wa[p].rnum == wa[q].rnum && wa[p].key <wa[q].key){
                    q <-->ls[t]; //q指示新的胜利者
                }
            }
            ls[0] = q;
        }
    }
    
    void Construct_Loser(LoserTree &ls,WorkArea &wa){
        //输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录并由s指示
        //其在wa中的位置
        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(RcdType),1,fi);    //输入一个记录
            wa[i].key = wa[i].rec.key;    // 提取关键字
            wa[i].rnum = 1;    //其段号为"1"
            Select_MiniMax(ls,wa,i);    //调整败者
        }
    }
    
    
    

    最佳归并树

    归并的过程可以用一棵树来形象地描述,这棵树称为归并树,
    为了优化归并树的带权路径长度,可以运用哈弗曼树。

     败者树

    为了突出如何利用败者树进行归并,在算法中避开了外存信息存取的细节,可以认为归并段已在内存。

    typedef int LoserTree[k];  //败者树是完全二叉树且不含叶子,可采用顺序存储结构
    typedef struct{
        KeyType key;
    }ExNode,External[k+1];    //外结点,只存放待归并记录的关键字
    
    void K_Merge(LoserTree &ls,External &b){
          /*利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。
    b[0]至b[k-1]为败者树上的k个叶子结点,分别存放k个输入归并段中当前记录的关键字。
    */
        for(i = 0;i<k; ++ i) input(b[i].key);       //分别从k个输入归并段读入该段当前第一个记录的关键字到外结点
        CreateLoserTree(ls);    //建败者树ls,选得最小关键字为b[ls[0]].key
        while(b[ls[0]].key != MAXKEY){
          q = ls[0];    //q指示当前最小关键字所在归并段
          output(q);  //将编号为q的归并段中当前(关键字为b[q].key)的记录写至输出归  并段
          input(b[q].key,q);// 从编号为q的输入归并段中读取下一个记录的关键字
          Adjust(ls,q);    //调整败者树,选择性的最小关键字
        }//while    
        output(ls[0]);    //将含最大关键字MAXKEY的记录写至输出归并段
    }
    
    
    void CreateLoserTree(LoserTree &ls){
          //已知b[0]到b[k-1]为完全二叉树ls的叶子结点存在k个关键字
    //,沿从叶子到根的k条路径将ls调整为败者树
        
        b[k].key  = MINKEY;    //设MINKEY为关键字可能的最小值
        for(i = 0;i < k;++i){
              ls[i] = k;    //设置ls中"败者"的初值
        }
        for(i = k-1; i>=0; - - i) Adjust(ls,i);   
     //依次从b[k-1],b[k-2],……,b[0]出发调整败者
       
    }
    
    while Adjust(LoserTree &ls,int s){
        //沿从叶子结点b[s]到根结点ls[0]的路径调整败者树
        t = (s+k)/2;
        while(t >0){
          if(b[s].key > b[ls[t]].key)  s<-->ls[t];    //s指示新的胜者
          t=t/2;
        }
        ls[0] = s;
    }
    

    由序号构造结点的好处是,不仅可以找到记录值,还可以找到其所在的归并段,以便于下一个记录读入内存取代刚选出的最值。

    为什么得用败者树,而不是用堆?:

    时间空间复杂度分析 

    外部排序的时间复杂度涉及很多方面,且分析较为复杂,一般考试不会让考试分析整个流程中与
    时间复杂度相关的每一个细节,因此只需要注意以下几点即可:
    
    1 m个初始归并段进行k路归并,归并的趟数为[logkm]
    2 每一次归并,所有记录都要进行两次I/O操作。
    3 置换-选择排序这一步中,所有记录都要进行两次I/O操作
    4 置换-选择排序中,选最值那一步的时间复杂度要根据考试要求的选择算法而定
    5 k路归并的败者树的高度为[log2k]+1,因此利用败者树从k个记录中选出最值需要进行[log2k]此比较,即 
      时间复杂度O(log2k)
    6 k路归并的败者树的建树时间复杂度为O(klog2k)
    注意k路归并败者树,不是k叉败者树,而是一颗二叉树
    

     空间复杂度
    显然所有步骤中的空间复杂度都是常量,因此是O(1)

     

    多路归并示例

     

      为了方便讲解,我们假设内存一共可以装4个int型数据。

             刚才我们是采取两两合并的方式,现在我们可以采取4个有序子串一起合并的方式,这样的话,每个数据从硬盘读写的次数各需要2次就可以了。如图:

     4个有序子串的合并,叫4路归并。如果是n个有序子串的合并,就把它称为n路归并。n并非越大越好。

    置换选择

             n不是越大越好,那么我们可以想办法减少有序子串的总个数。这样,也能减少数据从硬盘读写的次数。

             以前面的12个无序数据为例:

    例如我们可以从12个数据读取3个存到内存中,然后从内存中选出最小的那个数放进子串p1里;之后再从剩余的9个数据读取一个放到内存中,然后再从内存中选出一个数放进子串p1里,这个数必须满足比p1中的其他数大,且在内存中尽量小。这样一直重复,直到内存中的数都比p1中的数小,这时p1子串存放结束,继续来p2子串的存放,例如(这时假设内存只能存放3个int型数据):
     

    读入3个到内存中,且选出一个最小的到子串p1:

      这个时候已经没有符合要求的数了,且内存已满,进而用p2子串来存放,以此类推。

             通过这种方法,p1子串存放了4个数据,而原来的那种方法p1子串只能存放3个数据。

     

     这样子的话,最后只生成了2个有序子串,我们把这种方法称之为置换选择。按照这种方法,最好的情况下,所有数据只生成一个有序子串;最坏的情况下,和原来没采取置换选择算法一样,还是4个子串,那平均性能如何呢?

             结论:如果内存可以容纳n个元素的话,那么平均每个子串的长度为2m,也就是说,使用置换选择算法我们可以减少一半的子串数。

             这种方法适合要排序的数据太多,以至于内存一次性装载不下。只能通过把数据分几次的方式来排序,把这种方法称为外部排序。
    在这里插入图片描述

    展开全文
  • 通过改进的快速排序进行外部排序 您将为二进制数据实现外部排序算法。 输入数据文件将由许多 4 字节记录组成,每个记录由 1 到 30,000 范围内的两个 2 字节(短)整数值组成。 第一个 2 字节字段是键值(用于排序)...
  • 外部排序算法详解

    2014-10-29 12:24:29
    本PPT详细讲解了外部排序算法,讲解言简意赅,深入浅出,想了解外部排序算法的朋友可以下载阅读。
  • 有文件大小为1G的一个文件,文件每行存储的为URL及其访问次数,例如/api/auth/login 2 ,计算出访问次数最多的前5个URL和其访问次数,每行的URL可能重复,计算内存限制10M。 === 内含解题思路、测试结果截图、可运行...
  • 第十章 文件外部排序与搜索;主存储器和外存储器 文件组织 外排序 多级索引结构 可扩充散列 Trie树 ;主存储器与外部存储器;磁带tape;磁带卷在一个卷盘上运行时磁带经过读写磁头把磁带上的信息读入计算机或者把计算机...
  • 数据结构---归并排序和外部排序

    千次阅读 2019-04-23 19:11:39
    若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。 就地排序 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),称为就地排序。 稳定排序 ...

    内部排序
    若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。

    外部排序
    若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。

    就地排序
    若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),称为就地排序。

    稳定排序
    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序后,这些记录的相对次序保持不变,即在原序列中 ri=rj, ri 在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。

    排序序列分布
    排序需要考虑待排序关键字的分布情况,这会影响对排序算法的选择,通常我们在分析下列算法时都考虑关键字分布是随机分布的,不是按照某种规律分布的,比如正态分布等。

    待排序序列
    排序序列中,剩余即将要排序的序列部分。

    已排序序列
    排序序列中,已经排序好的序列部分

    首先我们了解一下归并排序的特性:

    1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
    2. 时间复杂度:O(N*logN)
    3. 空间复杂度:O(N)
    4. 稳定性:稳定
      归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有 序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤
    • 将我们的排序的数组进行我们的重点划分为两个部分
      例如left和right此时的区间是[left,right),制定一个中点mid = (left+right)/2。
    • 利用分治算法继续将我们左右两个继续进行划分,
    • 知道我们的left == right 或者left+1 == right,也就是只有一个元素的时候和一个元素也没有的时候我们就认为这个序列是有序的
    • 然后将我们的有序的数组进行合并,达到我们最后的时候就合成了有序的数组。
      在这里插入图片描述
      就上图一样,我们将数组每次拆解成两个部分,知道达到有序数组的条件的时候就开始合并我们的数组。这就是我们二路归并
      如下图所示,初始状态时,a序列[2,3,5]和b序列[2,9]为已排序好的子序列,现在利用二路归并,将a和b合并为有序序列 r,初始时,i指向a的第一个元素,j指向b的第一个元素,k初始值等于0。
      说明,r中最后一个元素起到哨兵的作用,灰色显示。

    在这里插入图片描述

    第一步,比较a[i]和b[j],发现相等,如果规定相等时,a的先进入r,则如下图所示,i, k分别加1,为了形象化,归并后的元素不再绘制。

    在这里插入图片描述

    第二步,继续比较,此时b[j]小,所以b的元素2进入r,则如下图所示,j, k分别加1,
    在这里插入图片描述

    第三步,继续比较,此时a[i]小,所以a的元素3进入r,则如下图所示,i, k分别加1,

    在这里插入图片描述

    第四步,继续比较,此时a[i]小,所以a的元素5进入r,则如下图所示,i, k分别加1,此时序列a的3个元素已经归并完,b中还剩下一个,这个可以通过k可以看出,它还没有到达个数5。
    在这里插入图片描述

    第五步,将序列b中的所有剩余元素直接放入r中即可,不用做任何比较了,直至b变空,二路归并结束。

    在这里插入图片描述

    这其实也就是和我们的第一个图解是一样的思想
    完整代码

    #include <iostream>
    using namespace std;
    void Swap(int arr[], int a, int b){
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    void combindArray(int array[], int left, int right, int mid){
    	//将[left,mid) 和数组[mid,right)进行合并
    	int* p = new int[right - left];
    	int i = 0;
    	int start = left;
    	int end = right;
    	int port = mid;
    	while (left < mid&&port < right){
    		if (array[left] < array[port]){
    			p[i++] = array[left++];
    		}
    		else{
    			p[i++] = array[port++];
    		}
    	}
    	while (left < mid){
    		p[i++] = array[left++];
    	}
    	while (port < right){
    		p[i++] = array[port++];
    	}
    	i = 0;
    	while (start < end){
    		array[start++] = p[i++];
    	}
    	delete[]p;
    }
    //1.平均切割区间
    //2.分治处理左右两个小区间,直到size ==0 或者size ==1
    //3.合并左右两个有序数组
    void MergeSortInner(int array[], int left, int right){//此时我们的区间是[left,right)
    	if (left == right){
    		return;//size=0;
    	}
    	if (left + 1 == right){
    		return;
    	}
    	int mid = (left + right) / 2;
    	MergeSortInner(array, left, mid);
    	MergeSortInner(array, mid, right);
    	//合并两个区间的元素
    	combindArray(array, left, right, mid);
    }
    //归并排序就是将两个有序的区间进行合并,采用分治算法
    void MergeSort(int array[], int size){
    	MergeSortInner(array, 0, size);
    }
    void printSort(int array[], int size){
    	for (int i = 0; i < size; i++){
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }
    int main(){
    	int arr[] = { 5, 6, 8, 9, 5, 4, 2, 3, 1, 6 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	MergeSort(arr, size);
    	printSort(arr, size);
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    
    
    

    了解外部排序
    数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
    比如我们对1000000个数据进行排序,此时内存不够的时候我们就不能进行内部排序,此时应该使用我们的外部排序的思想去进行排序。
    外部排序也是指的是大文件的排序,当待排序的文件很大时,无法将整个文件的所有记录同时调入内存进行排序,只能将文件存放在外存,这种排称为外部排序。外部排序的过程主要是依据数据的内外存交换和“内部归并”两者结合起来实现的。
    一般来说外排序分为两个步骤:预处理和合并排序。首先,根据可用内存的大小,将外存上含有n个纪录的文件分成若干长度为t的子文件(或段);其次,利用内部排序的方法,对每个子文件的t个纪录进行内部排序。这些经过排序的子文件(段)通常称为顺串(run),顺串生成后即将其写入外存。这样在外存上就得到了m个顺串(m=[n/t])。最后,对这些顺串进行归并,使顺串的长度逐渐增大,直到所有的待排序的记录成为一个顺串为止。
    1.预处理阶段
    最重要的事情就是选择初始顺串。通常使用的方法为置换选择排序,它是堆排序的一种变形,实现思路同STL的partial_sort。步骤如下:
    (1)初始化堆
    从磁盘读入M个记录放到数组RAM中;
    设置堆末尾标准LAST=M-1;
    建立最小值堆。
    (2)重复以下步骤直到堆为空
    把具有最小关键码值的记录Min也就是根节点送到输出缓冲区;
    设R是输入缓冲区中的下一条记录,如果R的关键码大于刚刚输出的关键码值Min,则把R放到根节点,否则使用数组中LAST位置的记录代替根节点,并将刚才的R放入到LAST所在位置,LAST=LAST-1;
    (3)重新排列堆,筛出根节点。
    如果堆的大小是M,一个顺串的最小长度就是M个记录,因为至少原来在堆中的那些记录将成为顺串的一部分,如果输入时逆序的,那么顺串的长度只能是M,最好情况输入是正序的,有可能一次性就能把整个文件生成一个顺串,由此可见生成顺串的长度是大小不一的,但是每个顺串却是有序的,利用扫雪机模型能够得到平均顺串的长度为2M。
    外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。
    2. 二路合并
    (1) 二路合并排序
    二路合并是最简单的合并方法,合并的实现与内排序中的二路归并算法并无本质区别,下面通过具体例子,分析二路合并外部排序的过程。
    有一个含有9000个纪录的文件需要排序(基于关键字)。假定系统仅能提供容纳1800个纪录的内存。文件在外存(如磁盘)上分块存储,每块600个纪录。外部排序的过程分为生成初始顺串和对顺串进行归并排序两个阶段。在生成初始顺串阶段,每次读入1800个纪录(即3段)待内存,采用内排序依次生成顺串依次写入外存储器中。
    顺串生成后,就开一开始对顺串进行归并。首先将内存等分成3个缓冲区,和,每个缓冲区可容纳600个纪录,其中和为输入缓冲区,为输出缓冲区,每次从外存读入待归并的块到和,进行内部归并,归并后的结果送入,中的几率写满时再将其写入外存。若(或)中的纪录为空,则将待归并顺串中的后续块读入和(或)中进行归并,直到待归并的两个顺串都已归并为止。重复上述的归并方法,由含有5块(每块上限1800个记录)的顺串经二路归并的一边归并后生成含有3块(每块上限3600个记录)的顺串,再经过第二遍……第s遍(s=[],m为初始顺串的个数),生成含有所有记录的顺串,从而完成了二路归并外部排序。
    对文件进行外部排序的过程中,因为对外存的读写操作所用的操作的时间远远超过在内存中产生顺串和合并所需的时间,所以常用对外存的读写操作所用的时间作为外部排序的主要时间开销。分析一下上述二路归并排序的对外存的读写时间。初始时生成5个顺串的读写次数为30次(每块的读写次数为2次)。
    类似地,可得到二路、三路……多路合并方法。
    (2) 多路替代选择合并排序
    采用多路合并技术,可以减少合并遍数,从而减少块读写次数,加快排序速度。但路数的多少依赖于内存容量的限制。此外,多路合并排序的快慢还依赖于内部归并算法的快慢。
    设文件有n个纪录,m个初始顺串,采用k路合并方法,那么合并阶段将进行遍合并。k路合并的基本操作是从k个顺换的第一个纪录中选出最小纪录(即关键字最小的纪录),把它从输入缓冲区移入输出缓冲区。若采用直接选择方式选择最小元,需要k-1次比较,遍合并共需n(k-1)=次比较。由于随k的增长而增长,则内部归并时间亦随k的增大而增大,这将抵消由于增大k而减少外存信息读写时间所得的效果。若在k个纪录中采用树形选择方式选择最小元,则选择输出一个最小元之后,只需从某叶到根的路径上重新调整选择树,即可选择下一个最小元。重新构造选择书仅用O()次比较,于是内部合并时间O(n)=O(),它与k无关,不再随k的增大而增大。
    常见的有基于“败者树”的多路替代选择合并排序方法。

    展开全文
  • 外部排序专题

    2020-12-03 13:14:21
    1.外部排序基本概念:前面介绍的排序都是内部排序,是直接在内存里面进行排序的,但是大多数情况下文件比较大,这时候我们就得把文件分割成一个个小块进行输入内存再排序。在排序过程中需要进行多次的内存与外存之间...

    1.外部排序基本概念:前面介绍的排序都是内部排序,是直接在内存里面进行排序的,但是大多数情况下文件比较大,这时候我们就得把文件分割成一个个小块进行输入内存再排序。在排序过程中需要进行多次的内存与外存之间的交互,所以称之为外部排序。

    外部排序操作:以例题作为讲解

    例题1:假设文件有4500个记录,每块磁盘可以放75个记录,计算机中用于排序的内存区可以存放 450 个记录,试问:
    1)可以建立多少个初始归并段?每个归并段有多少个记录?存放于多少个块中?
    2)应采用几路归并,请写出每趟需要读写磁盘的块数

    解答:
    1) 文件中有4500个记录,内部排序区可容纳450个记录(其实排序过程是 依次 输入1-450,451-900… 进行排序,然后输出构成有序的初始归并段 ),则可建立的初始归并段为4500/450 = 10,每个初始归并段有450个记录,存放于 450/75 =6 个块中。
    2)内存区可以容纳6个块,所以可以建立5个输入缓冲区。1个输出缓冲区,因此采用5路归并。
    归并次数为 log(5)10 = 2,每次归并需要读写磁盘次数都为4500/75=60 次 ,每次归并需要读写磁盘总次数为为60 * 2 =120 次,做了两趟归并,读写总次数 2 * 120=240。
    另外再来看看
    2.外部排序总时间= 内部排序所需时间+外村信息读写时间+内部归并需要时间

    内部排序所需时间 :就是第一次进行生成初始归并序列的时间,这其中就有一次读写时间,排序时间可以忽略。如上题内部排序所需时间为 120 相当于一次归并的时间
    外存信息读写时间 :其实就是归并次数乘以每次读写时间,上题为 两次归并,每次归并读写磁盘次数为120 ,所以总时间为2 * 120 = 240次。
    内部归并需要时间:就是在内存中进行序列段合并为一个序列段所需时间,这一时间其实主要在于数据进行比较的时间,例如上题,进行的是5路归并,那么在5个元素中选取最小数比较次数是4次,总共有4500个记录,最后一个不需要比较,因此每趟归并需要的比较次数为 (4500-1)*4=17996次,进行两次归并,17996 *2=35992次比较。但是比较时间相比于读写时间比较短所以可以忽略。

    归并次数 S=log(k) r 。r为初始归并段,k为归并路数,证明很简单,略。若是不采用其他方法进行比较次数优化则S趟总共需要比较次数为 S( n-1 )( k-1) = [ log(k) r ] ( n-1 )( k-1)=[log2 r] (n-1)(k-1)/[log2k] ,式子中 (k-1)/log2k 随着路数k的增大而增大,这将抵消由于k增大而减少外存访问次数所得到的效益,那么能不能使用其他方法来减少比较次数呢?下面介绍败者树方法。
    败者树:树中k个叶节点分别存放k个归并段在归并过程中当前参加比较的记录,内部节点用来记录左右子树的 “败者” 而胜利者继续向上比较直到到达根节点,如图所示。
    在这里插入图片描述

    因为 k 路归并的败者树深度为log2k , 因此k 个记录中选择最小关键字,最多需要 log2k次比较,所以排序总的比较次数为S(n-1)[log2k]=[log(k)r] (n-1) log2k=(n-1) log2r 。 可见使用败者树后内部归并的比较次数就与k无关了,因此只要内存空间允许,可以通过增大路数k达到减少 I/O 次数,提高外部排序速度。
    值得说明的是,归并路数k并不是越大越好,归并路数k增大,相应的得增加输入缓冲区的块数,若是可使用的空间一定,势必要减少每个输入缓冲区的容量,这样也会使得内存、外存交换数据次数增加,因此仍然会导致时间增大。

    还有什么办法可以减少排序时间呢?

    3.置换选择排序(生成初始归并段)
    只要增大初始归并段长度就可以减少初始归并段个数,达到减少归并时间的效果。

    在这里插入图片描述
    上述算法中WA选择最小数使用败者树实现。

    综上所述:每一次归并所读取 I/O 的次数是一定的,总记录/每块磁盘容量,因此可以通过减少归并次数,达到减少读取次数减少排序时间问题,那么减少归并次数的方法有:增大归并路数 或者 增大初始序列 。
    实现代码:

    
    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 > 0;t = t/2,p = ls[t]){
            // 段号小者 或者 段号相等且关键字更小的为胜者
            if(wa[p].rnum < wa[q].rnum || (wa[p].rnum == wa[q].rnum && wa[p].key < 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); // 调整败者树
        }
    }
    
    

    4.最佳归并树

    文件经过置换选择排序后,得到的是长度不等的初始归并段,下面讨论如何组织长度不等的初始归并段的归并顺序使得IO次数最少。其实也就是m叉哈夫曼树类似,很简单,不展开叙述。其中有一点不同是,可能初始归并段个数并不能构成严格的k叉树,这时就要补充虚段了。

    如何确定添加虚段的数目?
    设度为0的节点有 N0 个,度为 k的节点个数有Nk个,则对于严格k叉树 N0=(k-1) Nk+1,由此可得Nk=(N0-1)/(k-1) 。

    1. 若是(N0-1)%(k-1) =0 , 则说明这N0个叶节点正好可以构成严格k叉树。
    2. 若是不等于0,则设需要添加 m个 长度为0 的虚段使得(N0+m-1)%(k-1)=0,即可。

    以上就是外部排序的全部内容

    展开全文
  • 什么是外部排序

    2021-08-18 14:36:59
    外部排序外部排序的基本概念外部排序的方法后续 外部排序的基本概念 在内存中进行的排序是内部排序,而在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行...

    外部排序的基本概念

    在内存中进行的排序是内部排序,而在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行排序。因此,需要将待排序的记录存储在外存中,排序时再把数据一部分一部分地调入内存进行排序,在排序过程中需要多次进行内存和外存之间地交换。这种排序方法就称为外部排序。

    1. 外部排序指待排序文件较大,内存中一次性放不下,需存放在外存地文件地排序。
    2. 为减少平衡归并中外存读写次数所采取地方法:增大归并路数和减少归并段个数
    3. 利用败者树增大归并路数
    4. 利用置换-选择排序增大归并段长度来减少归并段个数
    5. 由长度不等地归并段,进行多路平衡归并,需要构造最佳归并树

    外部排序的方法

    文件通常是按块存储在磁盘上的,操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读 / 写的机械动作所需的时间远远超过内存运算的时间(相对而言可以忽略不记),因此在外部排序过程中的时间代价主要考虑访问磁盘的次数,即I/O次数。
    外部排序通常采用归并排序法。它包括两个相对独立的阶段:

    1. 根据内存缓冲区大小,将外存上的文件分成若干长度为t的子文件,依次读入内存并利用内部排序方法对他们进行排序,并将排序后得到的有序子文件重新写回外存,称这些有序子文件为归并段或顺串。
    2. 对这些归并段进行逐趟归并,是归并段逐渐由小到大,直至得到整个有序文件位置。

    在外部排序中实现两两归并时,由于不可能将两个有序段及归并结果段同时存放在内存中,因此需要不停地将数据读出、写入磁盘,而这会耗费大量的时间。一般情况下:
    外部排序的总时间 = 内存排序所需的时间 + 外存信息读取的时间 + 内部归并所需的时间
    显然,外村信息读取地时间远大于内部排序和内部归并地的时间,因此应着力减少I/O次数。由于外村信息的读/写是以“磁盘块”为单位进行的,以8个归并段为例,可知每一趟归并需进行16次读和16次写,3趟归并并加上内部排序时所需进行的读/写,使得总共需进行128次读写。若改用4路归并排序,则只需2趟排序,外部排序时的总读写次数便减少为96。
    因此增大归并路数可以减少归并趟数,进而减少总的磁盘I/O次数。

    一般的,对r个初始归并段,做K路平衡归并。
    K路平衡归并:

    1. 最多只能有k个段归并为一个
    2. 第一趟可将r个初始归并段归并为[r/k],以后每趟归并并将m个归并段归并成[m/k]个归并段,直至最后形成一个大的归并段位置。
    3. 树的高度 = [logkr]=归并趟数S。可见,只要增大归并路数k,或减少初始归并段个数r,都能减少归并趟数S,进而减少读写磁盘的次数,达到提高外部排序速度的目的。

    后续

    如果想了解更多物联网、智能家居项目知识,可以关注我的程序设计专栏
    订阅专栏后,可以在微信公众号上私聊我,直接发给你源码。
    或者关注公众号。
    在这里插入图片描述

    编写不易,感谢支持。

    展开全文
  • 八大内部排序+外部排序

    千次阅读 2019-07-12 21:42:21
    排序划分 内部排序 1.直接插入排序 基本思想 通常人们整理桥牌的方法是一张一张的来,将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中,为了要给插入的元素腾出空间,我们需要将其余所有元素...
  • 外部排序 C++源码

    2014-08-11 23:59:40
    原创,外部排序的C++源码,利用败者树16路归并,主要源于字典排序的需要,所以针对的是字符串,可以自定义字符串的最大最小长度,可以自定义归并路数,根据词组的大小,自定义设定内部排序的大小
  • Java实现外部排序

    千次阅读 2020-01-18 16:12:00
    外部排序使用场景及来源 主要针对大容量数据进行排序 在使用选择排序,插入排序,冒泡排序,和快速排序时的嘴馋时间复杂度是O(n^2),因此对于几十万的数据量时排序要耗费很长的时间。对于外部的文件进行数据排序,...
  • 外部排序算法总结

    万次阅读 多人点赞 2018-12-10 11:18:52
    我们一般提到排序都是指内排序,比如快速排序,堆排序,归并排序等,所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍,我们当然希望如果可以的话都是内排来完成。但对于大数据集来说,内存...
  • 排序算法之归并排序和外部排序

    千次阅读 2018-06-11 09:29:12
    一、归并排序   归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的...
  • 【数据结构】-排序-外部排序总结

    千次阅读 2020-07-04 18:00:54
    1.影响内部排序时间效率的是移动和比较的次数,影响外部排序时间效率的是i/o次数 2.减少平衡归并中i/o次数的有两个办法: 第一:增大归并路数 第二:减少归并段(有序段)个数 为了提高效率,我们考虑将归并路数...
  • Golang: 外部排序项目

    千次阅读 2018-08-13 22:47:49
    单机版外部排序 网络版外部排序 1. channel通信 // 向channel中发送数据 func ArraySource(a ...int) &amp;amp;amp;lt;-chan int { // 调用的真实情况是,函数新建一个channel并马上返回,并行的goroutine...
  • 考场上实现简单的外部排序代码,归并时采用二叉归并,实现简单易懂
  • 外部排序--归并算法实现

    千次阅读 2017-12-02 09:21:20
    #include #include<stdlib.h>//此部分直接硬写出来的,没参考网上...void sort(int num[], int n) //接受待排序数组和数组长度 { int tempnum = 1; int *temp; temp = (int*)malloc(n * sizeof(int)); //构建辅助
  • 本篇学习外部排序的基本概念,外部排序的主要排序算法及其原理。
  • 内部排序和外部排序小结

    千次阅读 多人点赞 2018-08-14 16:49:13
    简单选择排序、直接插入排序和冒泡排序的平均复杂度都为 O(n2),并且实现过程也较为简单,但是直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到 O(n),而简单选择排序则与序列的初始状态无关。...
  • 内部排序与外部排序简单比较

    万次阅读 2018-06-03 17:33:35
    前言本篇文章主要介绍内部排序与外部排序的知识,如果你和我一样还不知道内部排序和外部排序为何物的话,不妨看看我的理解正文由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两大类:...
  • 数据结构之外部排序:归并排序法

    千次阅读 2020-04-22 12:07:11
    外部排序:归并排序法外部归并排序的原理:外部归并排序的性能: 外部归并排序的原理: 第一步: 第二步: 问题:内存缓存区大小固定,外存数据元素分块后仍然无法将俩块放入比较 答:因为归并段已经块内有序,...
  • 数据结构内部排序和外部排序

    千次阅读 2019-01-22 21:27:04
    数据结构内部排序和外部排序1.1 概念1.2 衡量方法1.3 区分与汇总 1.1 概念 内排序:在排序过程中,所有元素调到内存中进行的排序。 外排序:待排序记录的数量很大,以致于内存不能一次容纳全部记录,所以在排序过程...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 222,460
精华内容 88,984
关键字:

外部排序