数据结构排序系列详解之六 树形选择排序

这篇博客接着来说说选择类排序之一的排序：树形选择排序

在简单选择排序中，每次的比较都没有用到上次比较的结果，所以比较操作的时间复杂度是O(N^2)，想要降低比较的次数，则需要把比较过程中的大小关系保存下来。树形选择排序是对简单选择排序的改进。

树形选择排序：又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

算法实现代码如下：

package exp_sort;

public class TreeSelectSort {

	public static int[] TreeSelectionSort(int[] mData) {
		int TreeLong = mData.length * 4;
		int MinValue = -10000;
		int[] tree = new int[TreeLong]; // 树的大小
		int baseSize;
		int i;
		int n = mData.length;
		int max;
		int maxIndex;
		int treeSize;
		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;
			}
		}
		return mData;
	}

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
		TreeSelectionSort(array);
		
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println("\n");
	}

}

算法分析：

在树形选择排序中，除了最小的关键字，被选出的最小关键字都是走了一条由叶子结点到跟节点的比较过程，由于含有n个叶子结点的完全二叉树的深度log2n+1,因此在树形选择排序中，每选出一个较小关键字需要进行log2n次比较，所以其时间复杂度是O(nlog2n)，移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)，与简单选择排序算法相比，降低了比较次数的数量级，增加了n-1个额外的存储空间存放中间比较结果。

在下一节中，我们说一种改进树形选择·排序的另一种排序方法——堆排序。