Data Structure-Select Sort-Tree Selection Sort
Published: 2019-05-05

Select Sort

1) The Locksmith sorting.

② Tree Selection Sort.←this

3 heapsort.


Tree Selection Sort (Tree Selection Sort), also known as Tournament Sort, is a method of selecting and sorting according to the idea of tournaments.

describe the process: firstly, compare the keywords of n records in pairs, and then compare the [n/2] (upper bound) larger (smaller) ones in pairs to select the record with the largest (smaller) keyword.Take out the largest (small) keyword, set it as INF, repeat the above, and select the next largest (small) keyword.(How do you feel so like Line segment tree?..)

Time complexity is 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
2365 (inverted original array)

After outputting 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

The following code uses to find the maximum value each time

#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;
}