堆排序（实现了从小到大排序和从大到小排序）

实现堆排序的方法类，具体的排序方法在heapAdjustMinToMax（该方法为从小到大）或heapAdjustMaxToMin（从大到小）中

package com.hcc.util;

/**
 * 实现堆排序的方法类
 * @author hcc
 *
 */
public class HeapSort {
    
    /**
     * 堆排序
     * @param arr 存放数据的数组
     * @param arrLength 数组的长度
     */
    public static void heapSortMinToMax(int[] arr,int arrLength) {
        
        for(int i = arrLength/2-1;i >= 0;i--) {
            //heapAdjustMinToMax(arr, i, arrLength);
            heapAdjustMaxToMin(arr, i, arrLength);
        }
        
        for(int i = arrLength-1;i >= 0;i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //heapAdjustMinToMax(arr, 0, i);
            heapAdjustMaxToMin(arr, 0, i);
        }
    }
    
    /**
     * 从小到大显示
     * 测试的数据 
     * 将数组以堆（本质是一棵完全二叉树）的形式构造
     * @param arr 存放数据的数组
     * @param s 
     * @param arrLength 数组的长度
     */
    private static void heapAdjustMinToMax(int[] arr,int s,int arrLength) {
        
        while(2*s+1 < arrLength) {
            int temp;
            int nextP = 2*s+1;
            if(nextP+1 < arrLength) {
                if(arr[nextP] < arr[nextP+1]) {
                    nextP++;
                }   
            }
            if(arr[s] < arr[nextP]) {
                temp = arr[nextP];
                arr[nextP] = arr[s];
                arr[s] = temp;
                s = nextP;
            }
            else {
                break;
            }           
        }
    }
    
    
    /**
     * 堆排序：从大到小
     * @param arr
     * @param s
     * @param arrLength
     */
    public static void heapAdjustMaxToMin(int[] arr,int s,int arrLength) {
        while(2*s+1 < arrLength) {
            int j = 2*s + 1;
            if(j+1 < arrLength) {
                if(arr[j] > arr[j+1]) {
                    j++;
                }
            }
            if(arr[s] > arr[j]) {
                int temp = arr[s];
                arr[s] = arr[j];
                arr[j] = temp;
                s = j;
            }else {
                break;
            }
        }
    }
}

测试类

package com.hcc.Test;

import com.hcc.util.HeapSort;

public class Test {

    public static void main(String[] args) {
        // 69 65 90 37 92 6 28 54  
        int[] arr = {69,65,90,37,92,6,28,54};
        int arrLength = arr.length;
        HeapSort.heapSortMinToMax(arr, arrLength);
        for(int i = 0;i < arrLength;i++) {
            System.out.print(arr[i]+" ");
        }
    }

}