您好,登录后才能下订单哦!
一、外排序
排序按数据存在的位置不同分为内排序和外排序
内排序:数据都在内存中,选择合适的排序方法对数据进行排序,比如选择排序、快速排序等
衡量内排序的效率是数据的比较次数
外排序:数据无法全部加载到内存中,只能不断在外部存储器和内存中进行交换完成排序
衡量外排序的效率是内存与外村的交换次数
外排序是针对大文件的数据排序,内存中无法加载这个大文件,把这个文件分为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"); }
后记:
堆结构:待处理的数据在树节点中(非叶子和叶子)
败者树结构:待处理的数据都只在叶子节点
堆结构适用于插入式无规则的,选出最值
败者树结构适用于多路序列插入,选出最值
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。