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

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

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

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

举例说明：

堆的性质：

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://择/冒泡/归并/希尔/快速排序算法过程工具：

http://tools.jb51.net/aideddesign/paixu_ys

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。