算法 堆排序

package net.com.heap;

import java.util.Arrays;

public class HeapSort {
/*
* fun将给定的一个数组创建成大頂堆
* array代表给定的数组，right代表数组的最大下标值
* */
public void createHeap(int[] array,int right){//创建大頂堆
int middle=right%2==0?right/2-1:right/2;
if(middle*2+2>right){//末尾的叶子节点不对称的情况
if(array[middle]<array[middle*2+1]){
int temp=array[middle];
array[middle]=array[middle*2+1];
array[middle*2+1]=temp;
}
middle=middle-1;
}
for(int i=middle;i>=0;i--){
if(array[i]<array[i*2+1] || array[i]<array[i*2+2]){
adjustHeap(array,right,i);
}

}
}
/*
* fun调整堆，使堆再次成为一个大頂堆
* array代表要调整的数组
* right代表数组的最大下标值
* currentIndex代表当前的不符合的节点的索引值
*/
public void adjustHeap(int array[],int right,int currentIndex){
while(currentIndex < right/2 && currentIndex*2+2<=right){
int leftChild=array[currentIndex*2+1];
int rightChild=array[currentIndex*2+2];
if(array[currentIndex] > leftChild && array[currentIndex] > rightChild){
break;
}else{
int temp=array[currentIndex];
int tempIndex=leftChild>rightChild?currentIndex*2+1:currentIndex*2+2;
array[currentIndex]=array[tempIndex];
array[tempIndex]=temp;
currentIndex=tempIndex;
}
}
if(currentIndex*2+2>right&&currentIndex<right/2){//对于节点不对称的情况进行的处理
if(array[currentIndex]<array[currentIndex*2+1]){
int temp=array[currentIndex];
array[currentIndex]=array[currentIndex*2+1];
array[currentIndex*2+1]=temp;
}
}
}
public void swap(int array[],int right){//将大頂堆的最大数与最后一个数作交换。
int temp=array[right];
array[right]=array[0];
array[0]=temp;
}
public void heapSort(int[]array,int right){
if(right>0){
swap(array,right);
adjustHeap(array,right-1,0);
heapSort(array,right-1);
}
/*if(array[1]<array[0]){
int temp=array[0];
array[0]=array[1];
array[1]=temp;
}*/
}
public static void main(String[]args){
HeapSort heapSort=new HeapSort();
int[] array={3,2,34,5,7,8,42,5};
int len=array.length;
heapSort.createHeap(array,len-1);
heapSort.heapSort(array, len-1);
System.out.println(Arrays.toString(array));
}
}