详解如何在Java中实现堆排序算法

算法描述

堆排序算法的描述如下：

• 将待排序的数组调整为最大堆，此时未排序的长度 N 为数组的长度，调整的过程就是倒序将数组的前 N/2 个元素下沉的过程，每次下沉都会将较大的元素带到上面，最终将数组变为最大堆；

• 弹出最大堆的堆顶元素并将其移动到数组的最后面，将原本最后面的元素放到堆顶，然后将未排序的长度 N - 1，调整数组的前 N 个元素为最大堆；

• 重复步骤 2 直到未排序的长度为 0.

实现代码

package com.zhiyiyo.collection.sort;

import java.util.Arrays;

public class HeapSort extends BaseSort {
   @Override
   public void sort(Comparable[] array) {
       int N = array.length;

// 创建最大堆
       for (int i = N / 2; i >= 0; i--) {
           sink(array, i, N);
       }

// 就地排序
       while (N > 0) {
           // 将最大的元素移动到数组的尾部，同时将未排序的长度-1
           swap(array, 0, --N);
           // 调整最大堆
           sink(array, 0, N);
       }
   }

/**
    * 下沉元素
    *
    * @param array 数组
    * @param k     下沉的元素索引
    */
   private void sink(Comparable[] array, int k, int N) {
       while (2 * k + 1 < N) {
           int j = 2 * k + 1;
           if (j < N - 1 && less(array[j], array[j + 1])) j++;
           if (!less(array[k], array[j])) break;
           swap(array, k, j);
           k = j;
       }
   }
}

抽象类 BaseSort 的代码为：

package com.zhiyiyo.collection.sort;

/**
* 数组排序抽象类
*/
public abstract class BaseSort {
   public abstract void sort(Comparable[] array);

/**
    * 交换数组元素
    *
    * @param array 数组
    * @param a     数组下标 a
    * @param b     数组下标 b
    */
   protected static void swap(Comparable[] array, int a, int b) {
       Comparable tmp = array[a];
       array[a] = array[b];
       array[b] = tmp;
   }

protected static boolean less(Comparable a, Comparable b) {
       return a.compareTo(b) < 0;
   }

}

测试代码

package com.zhiyiyo.collection.sort;

import org.junit.Test;

import java.util.Arrays;

public class HeapSortTest {

@Test
   public void sort() {
       Integer[] array = {5, 10, 9, 6, 8, 7, 2, 1, 4, 3};
       new HeapSort().sort(array);
       System.out.println(Arrays.toString(array));
   }
}

最终排序结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，以上~

来源：https://www.cnblogs.com/zhiyiYo/p/16042137.html