public class HeapSort {
public static void main(String []args){
int [] arr = {20,50,20,40,70,10,80,30,60};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
if (arr == null || arr.length<2){
return;
}
//构建大顶堆
for (int i = arr.length>>1; i >=0; i--) {
adjustHead(arr,i,arr.length);
}
//交换顶部文件并调整堆结构
for (int j = arr.length-1; j >0 ; j--) {
adjustHead(arr,0,j);
swap(arr,0,j);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void adjustHead(int[] arr, int i, int length) {
int temp = arr[i];
for (int j = i*2+1; j < length; j=j*2+1) {
if (j+1<length && arr[j]<arr[j+1]){
j++;
}
if (arr[j]>temp){
arr[i] = arr[j];
i = j;
} else {
break;
}
}
arr[i] = temp;
}
// private static void heapSort(int[] arr) {
//
// //构建大顶堆
// for (int i = arr.length/2; i >=0; i--) {
// adjustHeap(arr,i,arr.length);
// }
// //交换堆顶元素与末尾元素，调整堆结构
// for (int j = arr.length-1; j >0 ; j--) {
// swap(arr, 0,j);
// adjustHeap(arr,0,j);
// }
// }
//
// private static void swap(int[] arr, int i, int j) {
// int temp = arr[i];
// arr[i]= arr[j];
// arr[j]=temp;
// }
//
// private static void adjustHeap(int[] arr, int i, int length) {
//// int temp = arr[i];
//// for (int k = i*2+1; k < length; k = k*2+1) {
//// if (k+1<length && arr[k]<arr[k+1]){
//// k++;
//// }
//// if (arr[k]>temp){
//// arr[i]= arr[k];
//// i = k;
//// } else {
//// break;
//// }
//// }
//// arr[i] = temp;
//
// int temp = arr[i];
// for (int j = i*2+1; j < length; j=j*2+1) {
// if (j+1<length && arr[j]<arr[j+1]){
// j++;
// }
// if (arr[j]>temp){
// arr[i] = arr[j];
// i = j;
// } else {
// break;
// }
// }
// arr[i]= temp;
// }
}
