一、外排序

排序按数据存在的位置不同分为内排序和外排序

内排序：数据都在内存中，选择合适的排序方法对数据进行排序，比如选择排序、快速排序等

衡量内排序的效率是数据的比较次数

外排序：数据无法全部加载到内存中，只能不断在外部存储器和内存中进行交换完成排序

衡量外排序的效率是内存与外村的交换次数


外排序是针对大文件的数据排序，内存中无法加载这个大文件，把这个文件分为k个小文件，分别排序后合并


http://blog.csdn.net/msdnwolaile/article/details/52084983


二、败者树

胜者树和败者树都是完全二叉树，每个叶子节点相当于一个选手，每个中间节点相当于一场比赛，每一层相当于一轮比赛


胜者树的中间节点记录的是胜者的序号，败者树的中间节点记录的是败者的序号

1、胜者树

优点是：如果一个选手的数值改变，那么只需沿着一条路径（这个节点到根节点的路径）即可修正这颗胜者树


2、败者树

用中间节点记录败者，用另一个辅助节点记录胜者来进行下一场比赛

下面举一个栗子说明：




三、K路归并排序

我们把败者树分为两部分：

第一部分是b[]，用来保存K路数组的首元素，叶节点存放在此处

第二部分式ls[],用来保存败者数组的下标，b[0]是最终的胜者(即所求的数)，败者节点存放在此处

1、创建败者树

败者树


调整败者树

将新补充的节点与其父节点进行比较，败者留在该父节点上，胜者继续向上直至根节点


http://blog.sina.com.cn/s/blog_13a5c10be0102v1fb.html



#include<iostream>usingnamespacestd;constintMINKEY=0;//完全二叉树的叶子节点个数比度为2的节点个数多1voidAdjust(int*&b,int*&ls,inti,intk){//控制ls[]的下标intt=(i+k)/2;//第一个非叶子结点的下标、第二个。。。//控制b[]的下标ints=i;for(;t>0;t/=2){if(b[ls[t]]<b[s]){swap(s,ls[t]);}else{s=s;}}ls[0]=s;}voidcreateLoserTree(int*arr[],intk){//记录每个数组的首元素int*b=newint[k+1];//记录败者的下标int*ls=newint[k];//initb[]for(inti=0;i<k;++i)b[i]=arr[i][0];b[k]=MINKEY;//initls[]for(inti=0;i<k;++i)ls[i]=k;//最小值（绝对的胜者）的序号//有k个叶子节点//从最后一个叶子节点开始，沿着从叶子节点到根节点的路径调整for(inti=k-1;i>=0;--i){Adjust(b,ls,i,k);for(inti=0;i<k;++i)cout<<ls[i]<<"";cout<<endl;}}intmain(){/*intarr1[]={10,14,26,50};intarr2[]={9,22,38};intarr3[]={20,24,30};intarr4[]={6,15,25};intarr5[]={12,11,18};intarr6[]={90,92,97};int*arr[6]={arr1,arr2,arr3,arr4,arr5,arr6};createLoserTree(arr,6);*/intarr1[]={6,15,25};intarr2[]={12,37,48};intarr3[]={10,15,16};intarr4[]={9,18,20};intarr5[]={10,11,40};int*arr[]={arr3,arr4,arr5,arr1,arr2};createLoserTree(arr,5);system("pause");}/*//自己分析的过程。。。（较混乱，可不看）//createLoserTree()for(inti=k-1;k>=0;--k){Adjust(i);}//Adjust(i)intt=(i+k)/2;//第一个非叶子结点的下标ints=i;for(;t>=0;t/=2){if(b[ls[t]]<b[s]){s=ls[t];ls[t]=s;}else{s=s;}}//i=k-1if(b[ls[4]]<b[4]){s=ls[4]=5;//胜者ls[4]=4;}胜者编号是5elseif(b[ls[2]]<b[5])不成立elses=5//i=k-2if(b[ls[4]]<b[3])//不成立else{s=3}if(b[ls[2]]<b[3]){s=ls[2]=5ls[2]=3}if(b[ls[1]]<b[5])//不成立elses=5*/


2、K路归并排序

voidkMerge(int*arr[],int*arrayElementsCount,int&k,int*&ls,int*&b,int&mostMinCount){int*index=newint[k];for(inti=0;i<k;++i)index[i]=0;for(inti=0;i<mostMinCount;++i){ints=ls[0];cout<<b[s]<<"";++index[s];if(index[s]<arrayElementsCount[s])arr[s][0]=arr[s][index[s]];elsearr[s][0]=MAXKEY;b[s]=arr[s][0];Adjust(k,ls,b,s);}delete[]index;}


3、完整代码

#include<iostream>usingnamespacestd;constintMINKEY=0;//假设给定数组中所有数都大于0constintMAXKEY=200;//假设给定数组中所有数都小于200//完全二叉树的叶子节点个数比度为2的节点个数多1voidAdjust(int&k,int*&ls,int*&b,inti){//控制ls[]的下标intt=(i+k)/2;//第一个非叶子结点的下标、第二个。。。//控制b[]的下标ints=i;for(;t>0;t/=2){if(b[ls[t]]<b[s]){swap(s,ls[t]);}else{s=s;}}ls[0]=s;}voidcreateLoserTree(int*arr[],int&k,int*&ls,int*&b){//initb[]for(inti=0;i<k;++i)b[i]=arr[i][0];b[k]=MINKEY;//initls[]for(inti=0;i<k;++i)ls[i]=k;//最小值（绝对的胜者）的序号//有k个叶子节点//从最后一个叶子节点开始，沿着从叶子节点到根节点的路径调整for(inti=k-1;i>=0;--i){Adjust(k,ls,b,i);for(inti=0;i<k;++i)cout<<ls[i]<<"";cout<<endl;}}voidkMerge(int*arr[],int*arrayElementsCount,int&k,int*&ls,int*&b,int&mostMinCount){int*index=newint[k];for(inti=0;i<k;++i)index[i]=0;for(inti=0;i<mostMinCount;++i){ints=ls[0];cout<<b[s]<<"";++index[s];if(index[s]<arrayElementsCount[s])arr[s][0]=arr[s][index[s]];elsearr[s][0]=MAXKEY;b[s]=arr[s][0];Adjust(k,ls,b,s);}delete[]index;}intmain(){intarr0[]={6,15,25};intarr1[]={12,37,48,50};intarr2[]={10,15,16};intarr3[]={9,18,20};intarr4[]={10,11,40};//6,9,10,10,11,12,15,15,16,18,20,25,37,40,48,50int*arr[]={arr2,arr3,arr4,arr0,arr1};int*arrayElementsCount=newint[5];arrayElementsCount[0]=sizeof(arr2)/sizeof(arr2[0]);arrayElementsCount[1]=sizeof(arr3)/sizeof(arr3[0]);arrayElementsCount[2]=sizeof(arr4)/sizeof(arr4[0]);arrayElementsCount[3]=sizeof(arr0)/sizeof(arr0[0]);arrayElementsCount[4]=sizeof(arr1)/sizeof(arr1[0]);intk=sizeof(arr)/sizeof(arr[0]);//记录每个数组的首元素int*b=newint[k+1];//记录败者的下标int*ls=newint[k];createLoserTree(arr,k,ls,b);intmostMinCount=13;kMerge(arr,arrayElementsCount,k,ls,b,mostMinCount);delete[]b;delete[]ls;delete[]arrayElementsCount;system("pause");}



后记：

堆结构：待处理的数据在树节点中（非叶子和叶子）

败者树结构：待处理的数据都只在叶子节点

堆结构适用于插入式无规则的，选出最值

败者树结构适用于多路序列插入，选出最值