/**
*堆排序思路:O(nlogn)
* 用最大堆,传入一个数组,先用数组建堆,维护堆的性质
* 再把第一个数与堆最后一个数调换,因为第一个数是最大的
* 把堆的大小减小一
* 再 在堆的大小上维护堆的性质
* 重复操作..
*
*
*/
public class HeapSort
{
/**
*静态变量存放堆的大小
*/
private static int heapsize = 0 ;
/**
*堆排序主方法
* 构建最大堆,然后进行堆排序
* 堆排序是把最上面的最大的元素放在最下面,然后再维护上面最大堆的性质
*/
public static void heapSort(int[] resouceArr)
{
//堆的大小
heapsize = resouceArr.length - 1 ;
_buildMaxHeap(resouceArr);
for( int i = resouceArr.length - 1 ; i >= 0 ; i--)
{
int temp = resouceArr[0] ;
resouceArr[0] = resouceArr[i] ;
resouceArr[i] = temp ;
heapsize = heapsize - 1 ;
_maxHeapify( resouceArr, 0 );
}
}
/**
*构建最大堆
* 构建之后还不是有序的,但符合最大堆性质,上面的数一定大于下面的数
*/
private static void _buildMaxHeap(int[] arr)
{
int length = arr.length - 1 ;
//从倒数第二排开始维护最大堆性质
// 当heapsize为偶数时,heapsize要减一
// 当heapsize为奇数时,不变
if(length % 2 == 0)
{
length--;
}
for( int i = length / 2 ; i >= 0 ; i--)
{
_maxHeapify(arr , i );
}
}
/**
*用于维护堆的性质
* 树形堆在postion的位置向下维护堆的性质,自postion向下满足最大堆的性质
*/
private static void _maxHeapify(int[] arr,int postion)
{
//计算postion的左孩子和右孩子
postion = postion + 1 ;
int l = postion * 2 - 1;
int r = postion * 2 ;
postion = postion - 1 ;
int largest = maxNumInThreeNum(arr , postion , l , r);
//如果不满足最大堆性质,则交换值,然后检查树形下方是否满足最大堆性质
if(largest <= heapsize)
{
if( largest != postion)
{
//交换最大值与父节点值
int temp = arr[postion] ;
arr[postion] = arr[largest] ;
arr[largest] = temp ;
//如果子节点变动了,则重新构建已子节点为根的最大堆
_maxHeapify(arr , largest);
}
}
}
/**
*比较数组中的三个数找出最大值
*/
private static int maxNumInThreeNum(int[] arr ,int a, int b , int c)
{
int max = a ;
//数组长度小于左孩子,最大值为本身
if(heapsize < b)
{
max = a ;
}
else if(heapsize >=b && heapsize < c)
{
if(arr[a] < arr[b])
{
max = b ;
}
}
else
{
if(arr[a] > arr[b])
{
max = a ;
}
else
{
max = b ;
}
if(arr[max] < arr[c])
{
max = c ;
}
}
return max ;
}
}