`

排序算法篇(堆排序)

阅读更多
堆是一种特殊的数据结构,是一种完全二叉树,分为大根堆(根节点的值大于孩子节点)和小根堆(根节点小于孩子节点),建堆和堆排序代码如下:
package cn.com.daydayup.test;

public class StackSort {

    public static void main(String[] args) { 
        int[] a = { 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 }; 
        Sort(a); 
    } 
    //堆排需方法 
    public static void Sort(int[] a) { 
        int n = a.length;//取得数组总长度,及堆最大的序号 
        int temp = 0; 
 
        Display(a, "Before sort : "); 
        //这是建堆的过程,一次从倒数第二层的根节点开始调整堆,即数组下标为i/2开始,一直到顶层根节点,这样就建好堆了。。 
        for (int i = n / 2; i > 0; i--) { 
            Adjust(a, i - 1, n);//从倒数第二层的最后一个根节点开始调整堆 
            Display(a, "建立大根堆 : "); 
        } 
        System.out.println("---------------------------------------"); 
        for (int i = n - 2; i >= 0; i--) {//这是堆排序的具体算法,思想是每次取出堆的最顶层根节点,即数组下标为0,然后与最后一个节点即i+1交换,这样对于大根堆而言,最大值总是在后面。。循环过后就能排序了。。 
            temp = a[i + 1];//取出最后一个元素 
            a[i + 1] = a[0];//取出第一个元素,即顶层根节点 
            a[0] = temp;//交换位置 
 
            Adjust(a, 0, i + 1);//调整堆 
            Display(a, "重建立大根堆 : "); 
        } 
 
        Display(a, "After  sort : "); 
    } 
    /**
     * 调整堆的方法
     * @param a 要调整的数组,即堆
     * @param i 调整的根节点,即起始位置
     * @param n 要调整的终止位置
     */ 
    public static void Adjust(int[] a, int i, int n) { 
        int j = 0; 
        int temp = 0; 
 
        temp = a[i]; //取出根节点 
        j = 2 * i + 1;  //左孩子节点 
 
        while (j <= n - 1) { 
            if (j < n - 1 && a[j] < a[j + 1])//比较左右孩子,取出较大的孩子 
                j++; 
 
            if (temp >= a[j]) //如果根节点大于孩子节点则退出循环,不用调整 
                break; 
 
            a[(j - 1) / 2] = a[j];//较大的孩子节点值赋值给根节点 
 
            j = 2 * j + 1;//继续寻找左孩子 
        } 
 
        a[(j - 1) / 2] = temp;//将根节点赋值给最后一个空出来的节点 
    } 
    //打印堆内容 
    public static void Display(int[] a, String str) { 
        System.out.println(str); 
 
        for (int i = 0; i < a.length; i++) 
            System.out.print(a[i] + " "); 
 
        System.out.println(); 
    }

}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics