温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

外排序   败者树   多路归并

发布时间:2020-07-12 09:01:27 来源:网络 阅读:2320 作者:程红玲OOO 栏目:开发技术

一、外排序

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

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

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

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

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


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



后记:

堆结构:待处理的数据在树节点中(非叶子和叶子)

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

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

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

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI