简单堆排序

package com.jikeh.Heap;

/**

* 直接在原数组上进行原地的堆排序

*/

public class HeapSort {

private HeapSort(){}

public static void sort(Comparable[] arr){

int n = arr.length;

/**

* 注意：虽然是在原数组上进行直接Heapify，但是要把他想成一个堆

* Heapify过程：从最后一个非叶子节点开始

* 最后一个非叶子节点 = (最后一个元素的索引-1)/2

*/

for( int i = (n-1-1)/2 ; i >= 0 ; i -- ) {

shiftDown(arr, n, i);

}

/**

* 堆数组调整成有序的：最大元素始终处于0位置，然后循环与最后一个元素进行交换，再进行shiftDown

*/

for( int i = n-1; i > 0 ; i-- ){

swap( arr, 0, i);

shiftDown(arr, i, 0);

}

}

/**

* 元素交换

* @param arr

* @param i

* @param j

*/

private static void swap(Object[] arr, int i, int j){

Object t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

/**

* 堆排序的核心函数：

* @param arr

* @param n

* @param k

*/

private static void shiftDown(Comparable[] arr, int n, int k){

while( 2*k+1 < n ){

int j = 2*k+1;

if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 ) {

j += 1;

}

if( arr[k].compareTo(arr[j]) >= 0 ) {

break;

}

swap( arr, k, j);

k = j;

}

}

public static void main(String[] args) {

System.out.println("排序前：");

Integer[] arr = new Integer[10];

for(int i = 0; i < arr.length; i++){

arr[i] = new Integer((int) (Math.random() * 100));

System.out.print(arr[i]+" ");

}

System.out.println();

System.out.println("排序后：");

sort(arr);

for(int i = 0; i < arr.length; i++){

System.out.print(arr[i]+" ");

}

}

}