外排序   败者树   多路归并

一、外排序

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

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

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

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

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

外排序是针对大文件的数据排序，内存中无法加载这个大文件，把这个文件分为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");
}

后记：

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

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

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

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