堆排序

堆排序有以下需要注意的：

 

parent=n/2

left = 2 * n;

right = 2 * n + 1;

 

对某一个节点进行最大堆化

maxHeap

 

 

然后构造堆

buildHeap

 

最后是堆排序

heapSort

 

具体代码：

package com.taobao.saleengine.core.util;

public class HeapSort2 {

    private static int left(int i) { return i * 2;}
    private static int right(int i) { return i * 2 + 1;}
    private static void maxHeap(int[] a, int i, int length) {
        int l = left(i);
        int r = right(i);
        
        int largest = i;
        
        while(l<length && r<length) {
            if(a[l]>a[largest]) {
                largest = l;
            }
            if(a[r] > a[largest]) {
                largest = r;
            }
            
            if(largest != i) {
                int temp = a[largest];
                a[largest] = a[i];
                a[i] = temp;
                i = largest;
                l = left(i);
                r = right(i);
            } else {
                break;
            }
        }
    }
    
    private static void buildHeap(int a[], int length) {
        int start = length / 2 + 1;
        for(int i=start;i>=0;i--) {
            maxHeap(a, i, length);
        }
    }
    
    private static void heapSort(int a[]) {
        int length = a.length;
        buildHeap(a, length);
        while(length >= 1) {
            int temp = a[0];
            a[0] = a[length - 1];
            a[length - 1] = temp;
            maxHeap(a, 0, length - 1);
            length--;
        }
    }
    public static void printline(String s, int[] v) {
        System.out.println(s + toString(v));
    }

    public static String toString(int a[]) {
        StringBuilder s = new StringBuilder();
        for (int x : a)
            s.append(" ").append(x);
        return s.toString();
    }
    public static void main(String[] args) {
        int a[] = new int[] { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
        heapSort(a);
        printline("sorted ", a);
    }
}