选择排序
①简单选择排序。
②树形选择排序。←this
③堆排序。
树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort）是一种按照锦标赛的思想进行选择排序的方法。
描述过程：首先对n个记录的关键字进行两两比较，然后在其中[n/2]（取上界）个较大（小）者之间再进行两两比较，选出最大（小）关键字的记录为止。取出最大（小）关键字，将其设为INF，重复上面，选出次大（小）关键字。（咋感觉这么像线段树呢。。。）
时间复杂度为O(nlogn)
10
10 9
0 10 9 6
0 0 0 10 9 8 3 6
0 0 0 0 0 0 10 4 7 9 8 1 2 3 6 5（←倒着的原始数组）
输出10后
9
0 9
0 0 9 6
0 0 0 0 9 8 3 6
0 0 0 0 0 0 0 4 7 9 8 1 2 3 6 5
输出10，9后8
0 8
0 0 8 6
0 0 0 0 0 8 3 6
0 0 0 0 0 0 0 4 7 0 8 1 2 3 6 5
下面代码用的是每次找出最大值
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N=10; void print(int *tree){ int altm=0; for(int j=1;j<6;j++){ int tm=1; for(int i=1;i<j;i++) tm*=2; for(int i=1;i<=tm;++i) { printf("%d ",tree[altm+i]); } printf("\n");altm+=tm; } } void TreeSelectionSort(int *mData) { int MinValue = 0; int tree[N*4]; // 树的大小 int max,maxIndex,treeSize; int i,n = N,baseSize = 1; while (baseSize < n) baseSize *= 2; treeSize = baseSize * 2 - 1; //printf("treeSize:%d，baseSize:%d\n",treeSize,baseSize); for (i = 0; i < n; i++){//将要排的数字填到树上 tree[treeSize - i] = mData[i]; } for (; i < baseSize; i++){//其余的地方都填上最小值 tree[treeSize - i] = MinValue; } // 构造一棵树，大的值向上构造 for (i = treeSize; i > 1; i -= 2) { tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]); } n -= 1; while (n != -1) { max = tree[1]; //树顶为最大值 mData[n--] = max; //从大到小倒着贴到原数组上 maxIndex = treeSize; //最大值下标 //print(tree);//打印树 while (tree[maxIndex] != max){ maxIndex--; }//找最大值下标 tree[maxIndex] = MinValue; while (maxIndex > 1){ if (maxIndex % 2 == 0){ tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]); }else{ tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]); } maxIndex /= 2; } } } int main() { int a[N]={5,6,3,2,1,8,9,7,4,10}; TreeSelectionSort(a); for(int i=0;i<N;i++){ printf("%d ",a[i]); } return 0; }
