树形选择排序解释

树形选择排序 又称为锦标赛排序，其实理解起来很简单。

数组的 n 个元素就好像在进行锦标赛一样，每一轮小比赛每两个一组决出胜负(比较谁更小)。

再将每一轮的胜者每两个一组进行小比赛，直到最后决出唯一的胜者(即当前最小元素)。很明显，锦标赛构成图的形状就是一个满二叉树捏。

每一次锦标赛决出的最终胜者(最小元素)，我们要将其退出比赛，即放到原数组中。

重复上述操作，n 次锦标赛，即可完成排序。

那么具体如何实现呢？

我们需要用定义一个 tree[] 数组用来存储这个满二叉树。

首先我们需要录入叶子节点，也就是我们需要排序的数组中的所有元素。

然后根据二叉树在数组中的表示方法，我们知道若二叉树某个节点的下标为 i，可得其左孩子节点的下标为 2 * i + 1，右孩子节点下标为 2 * i + 2。

由此通过现有的叶子节点，可以得到其父节点的值，形象地说就是可以得到两个叶子节点的决胜者，即较小值。

当每次得到当前最小值，我们需要定义一个 minindex 在 tree[] 中寻找到当前这个最小值的索引，并将其置 MAX(这样就好像是它退出锦标赛了)

树形选择排序动态演示

我们以 [1, 4, 2, 3] 为例进行动态演示

第一次锦标赛得到决胜者

第二次锦标赛得到决胜者

第三次锦标赛得到决胜者

第四次锦标赛得到决胜者

树形选择排序时间复杂度

每次决出当前最小值，需要进行 log2n 次比较，总共需要进行 n 次锦标赛，所以时间复杂度

树形选择排序核心代码

void TreeSelectSort(int a[], int n){

    int nodesum = n * 2 - 1;  //满二叉树节点总数

    int *tree = new int[nodesum];

    /*	录入叶子节点	*/

    for(int i = n - 1, j = 0; i >= 0; i--, j++)

	tree[nodesum - j - 1] = a[i];

    /*	录入非叶子节点	*/

    for(int i = nodesum - n - 1; i >= 0; i--)

	tree[i] = tree[2 * i + 1] < tree[2 * i + 2] ? tree[2 * i + 1] : tree[2 * i + 2];

    /*	  每次找出最小元素并复制到原数组	 */

    int k = 0, minindex = -1;

    while(k < n){

        int min = tree[0];  //当前的树根节点值即为最小元素

	a[k++] = min;

	minindex = nodesum - 1;

	/* 从最后叶子节点开始，找到最小值位置，并将其置MAX */

	while(tree[minindex] != min)

	    minindex--;

	tree[minindex] = INT_MAX;

	/*	若此节点有父节点，将其兄弟节点值提升到父节点位置	*/

	while(minindex > 0){

	    if(minindex % 2 == 1){

	        //该节点为左节点

	        tree[(minindex - 1)/2] = tree[minindex] < tree[minindex + 1] ? tree[minindex] : tree[minindex + 1];

		minindex = (minindex - 1)/2;

	    }else{

		//该节点为右节点

		tree[minindex/2 - 1] = tree[minindex] < tree[minindex - 1] ? tree[minindex] : tree[minindex - 1];

		minindex = minindex/2 - 1;

	    }

	}

    }

    delete[] tree;

}

完整程序源代码

#include<iostream>

#include<ctime>

using namespace std;

void TreeSelectSort(int a[], int n){

    int nodesum = n * 2 - 1;  //满二叉树节点总数

    int *tree = new int[nodesum];

    /*	录入叶子节点	*/

    for(int i = n - 1, j = 0; i >= 0; i--, j++)

	tree[nodesum - j - 1] = a[i];

    /*	录入非叶子节点	*/

    for(int i = nodesum - n - 1; i >= 0; i--)

	tree[i] = tree[2 * i + 1] < tree[2 * i + 2] ? tree[2 * i + 1] : tree[2 * i + 2];

    /*	  每次找出最小元素并复制到原数组	 */

    int k = 0, minindex = -1;

    while(k < n){

        int min = tree[0];  //当前的树根节点值即为最小元素

	a[k++] = min;

	minindex = nodesum - 1;

	/* 从最后叶子节点开始，找到最小值位置，并将其置MAX */

	while(tree[minindex] != min)

	    minindex--;

	tree[minindex] = INT_MAX;

	/*	若此节点有父节点，将其兄弟节点值提升到父节点位置	*/

	while(minindex > 0){

	    if(minindex % 2 == 1){

	        //该节点为左节点

	        tree[(minindex - 1)/2] = tree[minindex] < tree[minindex + 1] ? tree[minindex] : tree[minindex + 1];

		minindex = (minindex - 1)/2;

	    }else{

		//该节点为右节点

		tree[minindex/2 - 1] = tree[minindex] < tree[minindex - 1] ? tree[minindex] : tree[minindex - 1];

		minindex = minindex/2 - 1;

	    }

	}

    }

    delete[] tree;

}

void show(int *a, int n){

    for(int i = 0; i < n; i++)

	cout<<*(a + i)<<" ";

    cout<<endl;

}

main(){

    int a[50];

    srand((int)time(0));

    int k = 0;

    while(k < 50)

	a[k++] = rand() % 100 + 1;

    show(a, 50);

    TreeSelectSort(a, 50);

    cout<<endl<<endl;

    show(a, 50);

}

巴特西

[排序算法] 树形选择排序 (C++)