亲宝软件园·资讯

展开

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

_almost_ 人气:0

本文实例讲述了java堆排序原理与实现方法。分享给大家供大家参考,具体如下:

堆是一个数组,被看成一个近似完全二叉树。

举例说明:

堆的性质:

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("测试结果:");
    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);
  }
}

代码中例子的运行结果:

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.softyun.net/aideddesign/paixu_ys

希望本文所述对大家java程序设计有所帮助。

加载全部内容

相关教程
猜你喜欢
用户评论