堆排序
逻辑结构 物理结构 动画效果
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcuYWNjRWM1ATNiNDZ2ATOxEWOjFmZ4kTO0U2YzIzNwcTOfdWbp9CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.png)
import org.apache.commons.lang.ArrayUtils;
/**
*
* 详细博文
* http://blog.csdn.net/jianyuerensheng/article/details/51263453
* 动图详细:
* http://jbcdn2.b0.upaiyun.com/2012/01/Visual-and-intuitive-feel-of-7-common-sorting-algorithms3.gif
*
* @author baoy
*
*/
public class HeapSort {
public static void main(String[] args) {
int[] array = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1 };
HeapSort.sort(array);
System.out.println(ArrayUtils.toString(array));
}
public static void sort(int[] a) {
// 循环建立初始堆,若父节点索引为i,那么左节点的索引为i*2+1,
//即左节点为a.length时,其父节点应当小于a.length/2
for (int i = a.length / 2; i >= 0; i--) {// 遍历存在子节点的父节点
adjustHeap(a, i, a.length - 1);
}
// 进行n-1次循环完成排序
for (int i = a.length - 1; i > 0; i--) {
// 最后一个元素和第一个元素进行交换
swap(a, i, 0);
adjustHeap(a, 0, i);
}
}
// 将数组转换为大根堆,大根堆的根节点为数组中的最大值
public static void adjustHeap(int[] a, int parent, int length) {
int temp = a[parent]; // 父节点的值
int child = 2 * parent + 1; // 左子节点的索引
while (child < length) {// 判断左节点是否为最大索引
// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
if (child + 1 < length && a[child] < a[child + 1]) {
child ++;// 将左子节点转换为右子节点
}
// 当父节点的值直接大于子节点的值时,直接退出
if (temp > a[child])
break;
// 将子节点的值赋值给父节点
a[parent] = a[child];
// 选取子节点的左子节点继续向下筛选
parent = child;
child = 2 * parent + 1;
}
// 若发生交换,此时parent代表子节点索引,没有发生交换,此时parent仍旧代表父节点索引
a[parent] = temp;
}
public static int[] swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return a;
}
}
捐助开发者
在兴趣的驱动下,写一个
免费
的东西,有欣喜,也还有汗水,希望你喜欢我的作品,同时也能支持一下。 当然,有钱捧个钱场(支持支付宝和微信 以及扣扣群),没钱捧个人场,谢谢各位。
个人主页:
http://knight-black-bob.iteye.com/谢谢您的赞助,我会做的更好!