堆排序的步骤:
- 构造堆
- 固定最大值再构造堆
java">public class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
java">public class HeapSort{
public static void main(String[] args){
int[] array = {9,8,7,6,5,4,3,2,1,0,-1};
System.out.println("Before heap:");
ArrayUtils.printArray(array);
heapSort(array);
System.out.println("After heap sort:");
ArrayUtils.printArray(array);
}
public static void heapSort(int[] array){
if(array==null || array.length <=1)
return;
buildMaxHeap(array);
for(int i=array.length-1;i>=1;i--){
ArrayUtils.exchangeElements(array,0,i);
maxHeap(array,i,0);
}
}
// 建堆的过程很简单,从下标 array.length 开始,
// 对每个结点都执行 maxHeap() 就行了,但是叶子结点由于没有子结点,
// 所以只需要从(array.length)/2开始
private static void buildMaxHeap(int[] array){
if(array==null || array.length <= 1){
return;
}
int half =array.length/2;
for(int i=half; i>=0;i--){
maxHeap(array,array.length,i);
}
}
private static void maxHeap(int[] array, int heapSize,int index){
int left=index*2+1; // 数组是从 index 0 开始的
int right =index*2+2;
int largest =index;
if(left<heapSize && array[left]>array[index]){
largest =left;
}
if(right <heapSize && array[right] > array[largest]){
largest = right;
}
if(index != largest){
ArrayUtils.exchangeElements(array,index,largest);
maxHeap(array.heapSize,largest);
}
}
}
参考博客:
- 堆排序(Heapsort)之Java实现:https://blog.csdn.net/kimylrong/article/details/17150475?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
- 堆排序Heap Sort——浅显易懂+Java实现:https://blog.csdn.net/sunnylinner/article/details/52585225
- 堆排序算法(图解详细流程):https://blog.csdn.net/u010452388/article/details/81283998