评论

收藏

[Java] java堆排序原理与实现方法分析

编程语言 编程语言 发布于:2021-10-06 12:56 | 阅读数:376 | 评论:0

这篇文章主要介绍了java堆排序原理与实现方法,结合实例形式分析了java堆排序的相关原理、实现方法与操作注意事项,需要的朋友可以参考下
本文实例讲述了java堆排序原理与实现方法。分享给大家供大家参考,具体如下:
堆是一个数组,被看成一个近似完全二叉树。
举例说明:
DSC0000.png DSC0001.png

堆的性质:
1.已知元素在数组中的序号为i
其父节点的序号为 i/2的整数
其左孩子节点的序号为2*i
其右孩子节点的序号为2*i+1
2.堆分为最大堆和最小堆
在最大堆中,要保证父节点的值大于等于其孩子节点的值
在最小堆中,要保证父节点的值小于等于其孩子节点的值
java实现堆排序
public class myheapsort {
  public void heap_sort(int[] a) {
  /**
   * 这个函数完成堆排序
   * 先构建一个最大堆
   * 将数组中第一个元素和最后一个交换,
   * 堆的长度减一
   * 在从第一个位置开始保证堆的性质调用max_heapify()函数。
   * 这样保证目前最大的元素在数组的最后位置。
   * 以此类推,直到最后一个元素。
   */
  build_max_heap(a);
  for (int i = a.length - 1; i >= 1; i--) {
    int temp = a[0];
    a[0] = a[i];
    a[i] = temp;
    max_heapify(a, 0, i);
  }
  }
  public void build_max_heap(int[] a) {
  /**
   * 这个函数用来构建堆
   * a:待排序的数组
   * (for循环中i的值从数组长度的一般开始取,是因为完全二叉树的性质,
   * 一半的节点叶根节点所以从叶节点开始向上遍历来保证堆的性质)
   */
  for (int i = a.length/2; i >= 0; i--) {
    max_heapify(a, i, a.length);
  }
  }
  public void max_heapify(int[] a, int i, int heap_size) {
  /**这个函数用来维护堆的性质,
   * 保证以序号为i的元素为根节点的子树中,父节点的值大于其孩子节点的值。
   * a:待排序数组
   * i:在数组a中的序号
   * heap_size:堆的大小
   */
  int largest = i;
  int l = i * 2 + 1;
  int r = i * 2 + 2;
  if (l < heap_size && a[l] > a[i]) largest = l;
  if (r < heap_size && a[r] > a[largest]) largest = r;
  if (largest != i) {
    int temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;
    max_heapify(a, largest, heap_size);
  }
  }
  public static void main(string[] args) throws exception {
  system.out.println("CodeAE代码之家测试结果:");
  int[] a = new int[]{1,3,2,5,34,23,44,15,67,45};
  new myheapsort().heap_sort(a);
  for (int x : a) system.out.println(x);
  }
}
代码中例子的运行结果:
DSC0002.png

希望本文所述对大家java程序设计有所帮助。
原文链接:https://blog.csdn.net/u014028027/article/details/78626416

关注下面的标签,发现更多相似文章