数据结构与算法——第10章-排序-树形选择排序(10.9)

发表于 2023-06-09 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 2 分钟

一概述

1
2
3

1.树形选择排序
2.树形选择排序图示
3.实现代码

二树形选择排序

树形选择排序（又称“锦标赛排序”），是一种按照锦标赛的思想进行选择排序的方法，
即所有记录采取两两分组，筛选出较小（较大）的值；
然后从筛选出的较小（较大）值中再两两分组选出更小（更大）值，
依次类推，直到最后选出一个最小（最大）值。同样可以采用此方式筛选出次小（次大）值等。

三树形选择排序图示

3.1 过程

1
2

整个排序的过程，可以用一棵具有 n 个叶子结点的完全二叉树表示。
例如对无序表{49，38，65，97，76，13，27，49}采用树形选择的方式排序，过程如下：

3.2 图示

一、步骤1

1
2
3

首先将无序表中的记录采用两两分组，筛选出各组中的较小值（如图 1 中的（a）过程）；
然后将筛选出的较小值两两分组，筛选出更小的值，
以此类推（如图 1 中的（b）（c）过程），最终整棵树的根结点中的关键字即为最小关键字：

二、步骤2

1
2

筛选出关键字 13 之后，继续重复此方式找到剩余记录中的最小值，此时由于关键字 13 已经筛选完成，
需要将关键字 13 改为“最大值”，继续重复此过程，如图 2 所示：

三、步骤3

1
2
3

通过不断地重复此过程，可依次筛选出从小到大的所有关键字。
该算法的时间复杂度为 O(nlogn)，同简单选择排序相比，
该算法减少了不同记录之间的比较次数，但是程序运行所需要的空间较多。

四实现代码

4.1 树形选择排序算法的 C 语言实现为

#include <stdio.h>
#include <string.h>
#define N 8
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;
	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; //最大值下标
		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] = { 49,38,65,97,76,13,27,49 };
	TreeSelectionSort(a);
	for (int i = 0; i < N; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

4.2 运行结果

1	13 27 38 49 49 65 76 97

五参考

C语言中文网—树形选择排序

0%