java数据结构排序算法之树形选择排序详解

2024-07-13 10:08:18

字体：大中小

来源：转载

供稿：网友

本文实例讲述了java数据结构排序算法之树形选择排序。分享给大家供大家参考，具体如下：

这里我们就来说说选择类排序之一的排序：树形选择排序

在简单选择排序中，每次的比较都没有用到上次比较的结果，所以比较操作的时间复杂度是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个额外的存储空间存放中间比较结果。

补充：

这里再来介绍对树形选择排序的改进算法，即堆排序算法。

堆排序弥补了树形选择排序算法占用空间多的缺憾。采用堆排序时，只需要一个记录大小的辅助空间。

算法思想是：

把待排序记录的关键字存放在数组r[1...n]中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以下每个记录r[2...n]依次逐层从左到右顺序排列，任意结点r[i]的左孩子是r[2*i]，右孩子是r[2*i+1]；双亲是r[[i/2]]。

堆定义：各结点的关键字值满足下列条件：

r[i].key >= r[2i].key 且 r[i].key >= r[2i+1].key (i=1,2,……[i/2])

满足上面条件的完全二叉树称为大根堆；相反，如果这颗完全二叉树中任意结点的关键字小于或者等于其左孩子和右孩子的关键字，对应的堆叫做小根堆。

堆排序的过程主要需要解决两个问题：第一个是，按照堆定义建初堆；第二个是，去掉最大元后重建堆，得到次大元。

堆排序即是利用堆的特性对记录序列进行排序,过程如下：

1、对给定序列建堆；
2、输出堆顶；(首元素与尾元素交换)
3、对剩余元素重建堆；(筛选首元素)
4、重复2，3，直至所有元素输出。

注意：“筛选”须从第[n/2]个结点开始，逐层向上倒退，直到根结点。