首页
登录 | 注册

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]个结点开始,逐层向上倒退,直到根结点。

算法分析:

1. 对深度为 k 的堆,“筛选”所需进行的关键字比较的次数至多为2(k-1);
2. n 个关键字的堆深度为  [log2n]+1, 初建堆所需进行的关键字比较的次数至多为:n* [log2n];
3. 重建堆 n-1 次,所需进行的关键字比较的次数不超过:(n-1)*2 [log2n ]; 

因此,堆排序在最坏情况下,其时间复杂度为O(nlog2n),这是堆排序的最大优点。

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

相关内容

相关文章

  • /** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ packa ...
  • 一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0 ...
  • 选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列. ...
  • 选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完.算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自 ...
  • 基本思想: 通过 n - i 次关键字间的比较,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序. 算法实现: <?php / ...

2019 xools.net webmaster#xools.net
12 q. 0.071 s.
湘ICP备19005923号