java实现堆排序

package com.peter.app.hello.heapsort;


/**
 * heap sort
 * @author Peter.Yu
 *
 */
public class HeapSort {


    public static int COUNT = 0;


    /**
     * build heap
     * @param a
     * @param size
     */
    public static void buildHeap(int[] a, int size) {
        for (int i = size / 2; i >= 1; i--) {
            adjustHeap(a, i, size);
        }
    }


    /**
     * adjust heap
     * @param a
     * @param i
     * @param size
     */
    public static void adjustHeap(int[] a, int i, int size) {
        int leftChild = i * 2;
        int rightChild = i * 2 + 1;
        int current = i;
        COUNT++;
        if (i <= size / 2) {
            if (leftChild <= size && a[leftChild] > a[current]) {
                current = leftChild;
            }
            if (rightChild <= size && a[rightChild] > a[current]) {
                current = rightChild;
            }
            if (current != i) {
                swap(a, i, current);
                adjustHeap(a, current, size);
            }
        }
    }


    /**
     * swap array element
     * @param a
     * @param i
     * @param j
     */
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


    /**
     * sort heap
     * @param a
     * @param size
     */
    public static void sortHeap(int[] a, int size) {
        buildHeap(a, size);
        for (int i = size; i >= 1; i--) {
            swap(a, 1, i);
            adjustHeap(a, 1, i - 1);
        }
    }


    /**
     * test
     * @param args
     */
    public static void main(String[] args) {
        int a[] = { 0, 0, 16, 20, 3, 11, 17, 8, 12 };
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
        sortHeap(a, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        System.out.println(COUNT);
    }
}

java实现堆排序,古老的榕树,5-wow.com