Java算法之堆排序代码示例

堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大。前一种称为最小堆,后一种称为最大堆。

比如下面这两个:

那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序。想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码:

public class HeapSort {
  private int[] numbers;
  private int length;
  public HeapSort(int[] numbers) {
    this.numbers = numbers;
    this.length = numbers.length;
  }
  /**
   * 调整二叉树
   * 如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1
   * 节点编号从1开始, 对应数组中的索引是编号-1
   * @param nodeId 节点编号, 从1开始
   */
  public void adjust(int nodeId) {
    int swapId;
    int flag = 0; //是否需要继续向下调整
    while(nodeId * 2 <= this.length && flag == 0) {
      //首先判断它和左子节点的关系, 并用swapId记录值较小的节点编号(最大堆是记录较大的)
      int index = nodeId - 1; //节点对应数组中数字的索引
      int leftChild = nodeId * 2 - 1; //左子节点对应数组中数字的索引
      int rightChild = nodeId * 2; //右子节点对应数组中数字的索引
      if(numbers[index] < numbers[leftChild]) {
        swapId = nodeId * 2;
      } else {
        swapId = nodeId;
      }
      //如果有右子节点, 再与右子节点比较
      if(nodeId * 2 + 1 <= this.length) {
        if(numbers[swapId - 1] < numbers[rightChild])
          swapId = nodeId * 2 + 1;
      }
      //如果最小的节点编号不是自己, 说明子节点中有比父节点更小的
      if(swapId != nodeId) {
        swap(swapId, nodeId);
        nodeId = swapId;
      } else {
        flag = 1;
      }
    }
  }
  /**
   * 交换两个节点的值
   * @param nodeId1
   * @param nodeId2
   */
  public void swap(int nodeId1, int nodeId2) {
    int t = numbers[nodeId1 - 1];
    numbers[nodeId1 - 1] = numbers[nodeId2 - 1];
    numbers[nodeId2 - 1] = t;
  }
  /**
   * 创建最大堆
   */
  public void createMaxHeap() {
    //从最后一个非叶节点到第一个节点依次向上调整
    for(int i = this.length / 2; i >= 1; i--) {
      adjust(i);
    }
  }
  public static void main(String[] args) {
    int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
    for(int x = 0; x < numbers.length; x++) {
      System.out.print(numbers[x] + " ");
    }
    System.out.println();
    HeapSort heap = new HeapSort(numbers);
    heap.createMaxHeap();
  }
}

对本例中的数列,从this.length / 2到1,共执行了三轮循环。

第一轮:

第二轮:

第三轮:

调整完成后,当前的二叉树已经符合最大堆的特性,可以用来从小到大排序。堆排序的原理是,交换堆顶和最后一个节点的数字,即把最大的数字放到数组最后,然后对除了最大数的前n-1个数从新执行调整过程,使其符合最大堆特性。重复以上过程直到堆中只剩下一个数字。

public void sort() {
  while(this.length > 1) {
    swap(1, this.length);
    this.length--;
    adjust(1);
  }
  for(int x = 0; x < numbers.length; x++) {
    System.out.print(numbers[x] + " ");
  }
}

堆排序的时间复杂度和快速排序的平均时间复杂度一样,是O(nlogn)。

总结

以上就是本文关于Java算法之堆排序代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:java实现的各种排序算法代码示例、Java遗传算法之冲出迷宫等,有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!

时间: 2017-11-06

Java数据结构及算法实例:插入排序 Insertion Sort

/** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

Java数据结构及算法实例:选择排序 Selection Sort

/** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

Java数据结构及算法实例:快速计算二进制数中1的个数(Fast Bit Counting)

/** * 快速计算二进制数中1的个数(Fast Bit Counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉 * 直到该数为0 * 中间循环的次数即为其中1的个数 * 例如给定"10100",减一后为"10011",相与为"10000",这样就消掉最右边的1 * Sparse Ones and Dense Ones were first described by Peter Wegner i

Java创建树形结构算法实例代码

在JavaWeb的相关开发中经常会涉及到多级菜单的展示,为了方便菜单的管理需要使用数据库进行支持,本例采用相关算法讲数据库中的条形记录进行相关组装和排序讲菜单组装成树形结构. 首先是需要的JavaBean import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Date; import j

Java数据结构及算法实例:冒泡排序 Bubble Sort

/** * 冒泡排序估计是每本算法书籍都会提到的排序方法. * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列. * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置, * 即每次把未排好的最大元素冒泡到序列最后端. * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始. * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素. * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置. * 由此可见冒泡排序的复杂

Java数据结构及算法实例:考拉兹猜想 Collatz Conjecture

/** * 考拉兹猜想:Collatz Conjecture * 又称为3n+1猜想.冰雹猜想.角谷猜想.哈塞猜想.乌拉姆猜想或叙拉古猜想, * 是指对于每一个正整数,如果它是奇数,则对它乘3再加1, * 如果它是偶数,则对它除以2,如此循环,最终都能够得到1. */ package al; public class CollatzConjecture { private int i = 1; public static void main(String[] args) { long l = 9

Java实现二分查找算法实例分析

本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

java实现Fibonacci算法实例

本文实例讲述了java实现Fibonacci算法的方法.分享给大家供大家参考.具体如下: package com.yenange.test2; import java.util.Scanner; public class Fibonacci { private static Scanner input = new Scanner(System.in); public static void main(String[] args) { System.out.println("-----------

java随机数生产算法实例

java提供了Math.random()函数,返回一个double类型的随机数,也有util包里的Random类,可以生成double,int,float,long,bytes等随机数. 但有些业务需求,往往需要对这些方法做一下封装.比如用固定因子生成32位的3DES算法key值. 下面提供一些封装的方法: package test; import java.util.Random; public class RandomUtil { public static final String ALL

Java TreeMap排序算法实例

本文实例讲述了Java TreeMap排序算法.分享给大家供大家参考,具体如下: TreeMap 和 HashMap 用法大致相同,但实际需求中,我们需要把一些数据进行排序: 以前在项目中,从数据库查询出来的数据放在List中,顺序都还是对的,但放在HashMap中,顺序就完全乱了. 为了处理排序的问题: 1. 对于一些简单的排序,如:数字,英文字母等 TreeMap hm = new TreeMap<String, String>(new Comparator() { public int

Java实现SHA-1算法实例

本文实例讲述了Java实现SHA-1算法的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class SHA1Util {     private static final boolean hexcase = false;     private static final String b64pad = "=";     private static final int chrsz = 8;     // 得到字符串SHA-1值的方法     pub

Java分治归并排序算法实例详解

本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

Java数据结构及算法实例:朴素字符匹配 Brute Force

/** * 朴素字符串算法通过两层循环来寻找子串, * 好像是一个包含模式的"模板"沿待查文本滑动. * 算法的思想是:从主串S的第pos个字符起与模式串进行比较, * 匹配不成功时,从主串S的第pos+1个字符重新与模式串进行比较. * 如果主串S的长度是n,模式串长度是 m,那么Brute-Force的时间复杂度是o(m*n). * 最坏情况出现在模式串的子串频繁出现在主串S中. * 虽然它的时间复杂度为o(m*n),但在一般情况下匹配时间为o(m+n), * 因此在实际中它被大量

Java数据结构及算法实例:汉诺塔问题 Hanoi

/** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱