1.介绍
树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛思想进行选择排序的不稳定排序。
2.实现原理
如图所示，给定有8个元素的数组，对该数组进行从小到大的排序。
第一步，如图所示，根据数组建立一颗满二叉树（胜者树），用于进行’锦标赛事’的多层次比较。所有的数组元素如同打锦标赛一样全部位于二叉树的叶子节点上，因为是满二叉树，所以所有的数组元素都位于最底层，请读者自行思考。元素数量不足时，用空节点补齐。
第二步，如图所示，像锦标赛一样，让相邻节点相互’pk’，把数值较小的节点”晋升”到其父节点上，注意，这一排序目标是从小到大，因此是较小的移到父节点，反之，则是较大的移到父节点。
如此一来，聪明的读者一定可以自己推出第一次打完锦标赛时树的样子了，如图所示，显而易见，树的根节点的值最小，就像锦标赛中冠军一定是本赛季最强的一个道理。
选出最小值后，将该叶子节点删除（设为无穷大），接着继续打锦标赛（选手们不累吗），当然选手们并不用那么辛苦，我们不必对整棵树进行操作，因为第二小的值一定是在和第一小的值对峙时败下阵来的，因此第二小的数一定在第一小的晋升的路上，所以只需在这条路上再选出一个第一小的数就行了（图就不画了，太难受了）。
重复上述步骤n轮你就成功的排好序了，Oh Yeah！
3.算法复杂度分析
创建和填充二叉树仅需O(n),后继每一轮进行局部刷新二叉树需要O(logn),共进行n-1轮，因此总的时间复杂度为：O(nlogn);
由于二叉树的结点数量和数组元素个数成正比，所以空间复杂度为O(n)。相对于选择排序，锦标赛排序有效地降低了时间复杂度，但使用的辅助存储空间较多，和∞的比较多余。
实际编程时，除叶子结点外，并不需要在其它结点保存刷新的元素值，可以使用辅助数组idx[]保存刷新的元素值的原始下标位置即可。如图所示，数组idx[]初始化时，idx[8]＝0表示结点8的值为a[0]，idx[9]＝1表示结点9的值为a[1]……
假设现在更新结点7 的值，因为左子结点的编号为14 （即7<
\完结撒花!!!/
等等……是不是漏了些什么……
4.参考程序
1 #include2 #define INF 0x3f3f3f 3 using namespace std; 4 int a[1000100],idx[1000100]; 5 int siz = 1; 6 void Adjust(int p,int Ls,int Rs){ 7 idx[p] = a[idx[Ls]]idx[Ls]:idx[Rs]; 8 } 9 int main(){ 10 int n; 11 cin>>n; 12 while (siz<n){ 13 siz<1; //siz*=2; 14 } 15 for (int i=0;i ){ 16 cin>>a[i]; 17 idx[i+siz] = i; //辅助数组记录数组下标 18 } 19 for (int i=n;i ;i++[idx[rs]]?){ 20 a[i] = INF; //空节点设为无穷大（ 21 idx[i+siz] = i; 22 } 23 for (int i = siz-1;i;i--) 24 Adjust(i,i<<1,(i<<1)+1); //节点，左儿子，右儿子下标 25 for (int i=0;i ;i++){ 26 cout<1]]<<' '; //输出 27 a[idx[1]] = INF; 28 for (int j=(idx[1]+siz)>>1;j;j>>=1){ 29 Adjust(j,j<<1,(j<<1)+1); 30 } 31 } 32 return 0; 33 }[idx[ ;i++
Original: https://www.cnblogs.com/reasa/p/16654283.html
Author: reasa
Title: 锦标赛排序（树形选择排序）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587527/
转载文章受原作者版权保护。转载请注明原作者出处！