外排序 败者树 多路归并
一、外排序
排序按数据存在的位置不同分为内排序和外排序
内排序：数据都在内存中，选择合适的排序方法对数据进行排序，比如选择排序、快速排序等
衡量内排序的效率是数据的比较次数
外排序：数据无法全部加载到内存中，只能不断在外部存储器和内存中进行交换完成排序
衡量外排序的效率是内存与外村的交换次数
外排序是针对大文件的数据排序，内存中无法加载这个大文件，把这个文件分为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>
using namespace std;
const int MINKEY = 0;
//完全二叉树的叶子节点个数比度为2的节点个数多1
void Adjust(int* &b,int* &ls,int i,int k)
{
//控制ls[]的下标
int t = (i + k) / 2;//第一个非叶子结点的下标、第二个。。。
//控制b[]的下标
int s = i;
for (; t > 0; t /= 2){
if (b[ls[t]]<b[s]){
swap(s, ls[t]);
}
else{
s = s;
}
}
ls[0] = s;
}
void createLoserTree(int* arr[],int k)
{
//记录每个数组的首元素
int* b = new int[k+1];
//记录败者的下标
int* ls = new int[k];
//init b[]
for (int i = 0; i < k; ++i)
b[i] = arr[i][0];
b[k] = MINKEY;
//init ls[]
for (int i = 0; i < k; ++i)
ls[i] = k;//最小值（绝对的胜者）的序号
//有k个叶子节点
//从最后一个叶子节点开始，沿着从叶子节点到根节点的路径调整
for (int i = k - 1; i >= 0; --i){
Adjust(b, ls, i, k);
for (int i = 0; i < k; ++i)
cout << ls[i] << " ";
cout << endl;
}
}
int main()
{
/*int arr1[] = { 10, 14, 26, 50 };
int arr2[] = { 9, 22, 38 };
int arr3[] = { 20, 24, 30 };
int arr4[] = { 6, 15, 25 };
int arr5[] = { 12, 11, 18 };
int arr6[] = { 90, 92, 97 };
int* arr[6] = { arr1, arr2, arr3, arr4, arr5, arr6 };
createLoserTree(arr, 6);*/
int arr1[] = { 6, 15, 25 };
int arr2[] = { 12, 37, 48 };
int arr3[] = { 10, 15, 16 };
int arr4[] = { 9, 18, 20 };
int arr5[] = { 10, 11, 40 };
int* arr[] = { arr3, arr4, arr5, arr1, arr2 };
createLoserTree(arr, 5);
system("pause");
}
/*//自己分析的过程。。。（较混乱，可不看）
//createLoserTree()
for (int i = k - 1; k >= 0; --k){
Adjust(i);
}
//Adjust(i)
int t = (i + k) / 2;//第一个非叶子结点的下标
int s = i;
for (; t >= 0; t /= 2){
if (b[ls[t]]<b[s]){
s = ls[t];
ls[t] = s;
}
else{
s = s;
}
}
//i=k-1
if (b[ls[4]]<b[4]){
s = ls[4] = 5;//胜者
ls[4] = 4;
}胜者编号是5
else
if (b[ls[2]]<b[5])不成立
else
s = 5
//i=k-2
if (b[ls[4]]<b[3])//不成立
else{
s = 3
}
if (b[ls[2]]<b[3]){
s = ls[2] = 5
ls[2] = 3
}
if (b[ls[1]]<b[5])//不成立
else
s = 5*/
2、K路归并排序
void kMerge(int* arr[], int* arrayElementsCount, int& k, int* &ls, int* &b, int& mostMinCount)
{
int* index = new int[k];
for (int i = 0; i < k; ++i)
index[i] = 0;
for (int i = 0; i < mostMinCount; ++i){
int s = ls[0];
cout << b[s] << " ";
++index[s];
if (index[s] < arrayElementsCount[s])
arr[s][0] = arr[s][index[s]];
else
arr[s][0] = MAXKEY;
b[s] = arr[s][0];
Adjust(k, ls, b, s);
}
delete[] index;
}
3、完整代码
#include <iostream>
using namespace std;
const int MINKEY = 0;//假设给定数组中所有数都大于0
const int MAXKEY = 200;//假设给定数组中所有数都小于200
//完全二叉树的叶子节点个数比度为2的节点个数多1
void Adjust(int &k, int* &ls, int* &b, int i)
{
//控制ls[]的下标
int t = (i + k) / 2;//第一个非叶子结点的下标、第二个。。。
//控制b[]的下标
int s = i;
for (; t > 0; t /= 2){
if (b[ls[t]]<b[s]){
swap(s, ls[t]);
}
else{
s = s;
}
}
ls[0] = s;
}
void createLoserTree(int* arr[],int &k, int* &ls, int* &b)
{
//init b[]
for (int i = 0; i < k; ++i)
b[i] = arr[i][0];
b[k] = MINKEY;
//init ls[]
for (int i = 0; i < k; ++i)
ls[i] = k;//最小值（绝对的胜者）的序号
//有k个叶子节点
//从最后一个叶子节点开始，沿着从叶子节点到根节点的路径调整
for (int i = k - 1; i >= 0; --i){
Adjust(k, ls, b, i);
for (int i = 0; i < k; ++i)
cout << ls[i] << " ";
cout << endl;
}
}
void kMerge(int* arr[], int* arrayElementsCount, int& k, int* &ls, int* &b, int& mostMinCount)
{
int* index = new int[k];
for (int i = 0; i < k; ++i)
index[i] = 0;
for (int i = 0; i < mostMinCount; ++i){
int s = ls[0];
cout << b[s] << " ";
++index[s];
if (index[s] < arrayElementsCount[s])
arr[s][0] = arr[s][index[s]];
else
arr[s][0] = MAXKEY;
b[s] = arr[s][0];
Adjust(k, ls, b, s);
}
delete[] index;
}
int main()
{
int arr0[] = { 6, 15, 25 };
int arr1[] = { 12, 37, 48, 50 };
int arr2[] = { 10, 15, 16 };
int arr3[] = { 9, 18, 20 };
int arr4[] = { 10, 11, 40 };
//6,9,10,10,11,12,15,15,16,18,20,25,37,40,48,50
int* arr[] = { arr2, arr3, arr4, arr0, arr1 };
int* arrayElementsCount = new int[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]);
int k = sizeof(arr) / sizeof(arr[0]);
//记录每个数组的首元素
int* b = new int[k + 1];
//记录败者的下标
int* ls = new int[k];
createLoserTree(arr, k,ls,b);
int mostMinCount = 13;
kMerge(arr, arrayElementsCount, k, ls, b, mostMinCount);
delete[] b;
delete[] ls;
delete[] arrayElementsCount;
system("pause");
}
后记：
堆结构：待处理的数据在树节点中（非叶子和叶子）
败者树结构：待处理的数据都只在叶子节点
堆结构适用于插入式无规则的，选出最值
败者树结构适用于多路序列插入，选出最值