public class HeapSort {
1.
2. public static void sort(Comparable[] data) {
3. // 构建最大堆
4. buildMaxHeap(data);
5. // 循环，每次把根节点和最后一个节点调换位置 后面的扔了搞前面的
6. for (int i = data.length; i > 1; i--) {
7. Comparable tmp = data[0];
8. data[0] = data[i - 1];
9. data[i - 1] = tmp;
10.
11. // 堆的长度减少1，排除置换到最后位置的根节点
12. maxHeapify(data, 1, i - 1);
13. }
14. }
15.
16. // 根据输入数组构建一个最大堆
17. private static void buildMaxHeap(Comparable[] data) {
18. for (int i = data.length / 2; i > 0; i--) {
19. maxHeapify(data, i, data.length);
20. }
21. }
22.
23. //堆调整，使其生成最大堆
24. private static void maxHeapify(Comparable[] data, int parentNodeIndex, int heapSize) {
25. // 左子节点索引
26. int leftChildNodeIndex = parentNodeIndex * 2;
27. // 右子节点索引
28. int rightChildNodeIndex = parentNodeIndex * 2 + 1;
29. // 最大节点索引
30. int largestNodeIndex = parentNodeIndex;
31.
32. // 如果左子节点大于父节点，则将左子节点作为最大节点
33. if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1].compareTo(data[parentNodeIndex - 1]) > 0) {
34. largestNodeIndex = leftChildNodeIndex;
35. }
36.
37. // 如果右子节点比最大节点还大，那么最大节点应该是右子节点
38. if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1].compareTo(data[largestNodeIndex - 1]) > 0) {
39. largestNodeIndex = rightChildNodeIndex;
40. }
41.
42. // 最后，如果最大节点和父节点不一致，则交换他们的值
43. if (largestNodeIndex != parentNodeIndex) {
44. Comparable tmp = data[parentNodeIndex - 1];
45. data[parentNodeIndex - 1] = data[largestNodeIndex - 1];
46. data[largestNodeIndex - 1] = tmp;
47.
48. // 交换完父节点和子节点的值，对换了值的子节点检查是否符合最大堆的特性
49. maxHeapify(data, largestNodeIndex, heapSize);
50. }
51. }
52.
53. }
package com.wyq.HeapSort;
public class HeapSort{
private static int[] array=new int[]{9,3,5,2,7,1,3,12};
public static void main(String[] args){
buildMaxHeapify(array);
heapSort(array);
print(array);
}
private static void buildMaxHeapify(int[] data){ //创建最大堆
//没有子节点的才需要创建最大堆，从最后一个的父节点开始
int startIndex=getParentIndex(data.length-1);
//从尾端开始创建最大堆，每次都是排好的堆
for(int i=startIndex;i>=0;i--){
maxHeapify(data,data.length,i);//创建最大堆的方法
}
}
/**
*创建最大堆
*
*@paramdata
*@paramheapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
*@paramindex当前需要创建最大堆的位置
*/
private static void maxHeapify(int[] data,int heapSize,int index){
//当前点与左右子节点比较
int left=getChildLeftIndex(index);//获取左子节点
int right=getChildRightIndex(index);//获取右子节点
int largeMoreindex=index;
if(left<heapSize&&data[index]<data[left]){
largeMoreindex=left;
}
if(right<heapSize&&data[largeMoreindex]<data[right]){
largeMoreindex=right;
}
//得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
if(largeMoreindex!=index){//交换位置
int temp=data[index];
data[index]=data[largeMoreindex];//
data[largeMoreindex]=temp;
maxHeapify(data,heapSize,largeMoreindex);
}
}
/**
*排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
*
*@paramdata
*/
private static void heapSort(int[] data){
//末尾与头交换，交换后调整最大堆
for(int i=data.length-1;i>0;i--){
int temp=data[0];
data[0]=data[i];
data[i]=temp;
maxHeapify(data,i,0);
}
}
/**
*父节点位置
*
*@paramcurrent
*@return
*/
private static int getParentIndex(int current){
return(current-1)>>1;//右移相当于除以2
}
/**
*左子节点position注意括号，加法优先级更高
*
*@paramcurrent
*@return
*/
private static int getChildLeftIndex(int current){
return current*2+1;
}
/**
*右子节点position
*
*@paramcurrent
*@return
*/
private static int getChildRightIndex(int current){
return current*2+2;
}
private static void print(int[] data){
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
}
}
HeapSort