堆排序

堆排序

 

逻辑结构                             物理结构                                  动画效果

 

 

 

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/

 
 
 谢谢您的赞助，我会做的更好！