算法实现-堆排序

package com.sort;

 

public class HeapSort {

/**

* 将整棵树构建为最大堆

* @param a

*/

public void builMaxHeap(int[] a){

int length = a.length-1;//堆排序数据长度,第一个数据不使用,设置为0,哨兵值

int heapSize = length/2;

for(;heapSize > 0 ;heapSize--){

maxHeapfy(a,heapSize);

}

}

/**

* 将子树构建为最大堆

* @param a

* @param root

*/

public void maxHeapfy(int[] a,int root){

int largest = root;

int left = 2*largest;

int right = 2*largest +1;

if(left>a.length-1){//当左子树大于数组最后一个元素的下标时,直接返回

return;

}else if(left == a.length-1){//当左子树等于数组最后一个元素的下标时,比较数组

if(a[root]<a[left]){

int tmp = a[root];

a[root] = a[left];

a[left]= tmp;

}

return;

}

//其他情况则表示存在右节点,按照一颗完整子树去比较根节点与左右子树的大小

if(a[largest]<a[left]){

largest = left;

}

if(a[largest]<a[right]){

largest = right;

}

if(root != largest){//保持树中的根节点为最大值

int tmp;

tmp = a[root];

a[root] = a[largest];

a[largest] = tmp;

}else if(root == largest){//如果根节点为最大值

if(a[left]>a[right]){//比较左右子树的大小

largest = left;

}else{

largest = right;

}

}

//largest = largest + 1;

maxHeapfy(a,largest);

}

/**

* 堆排序算法

* @param a

* @return

*/

public int[] heapSort(int[] a){

this.builMaxHeap(a);

int length = a.length-1;

int[] b = new int[a.length];

b[0] = -1;//哨兵值,这个树不参与排序,和a数组中第一个值保持一致

for(int i=length;i>0;i--){//循环将树重新构建成最大堆

b[i] = a[1];//将新构建的最大堆中根节点赋值给数组b

a[1] = -1;//将根节点赋值无用的-1标记

this.maxHeapfy(a, 1);//重新构建堆

}

return b;

}

public static void main(String[] args) {

int[] a = new int[]{-1,4,1,3,2,16,22,23,0,25,25,25,9,10,14,8,1000};

HeapSort heapSort = new HeapSort();

int[] b = heapSort.heapSort(a);

for(Integer sortHeap:b){

System.out.println(sortHeap);

}

}

 

}