算法描述

堆排序算法的描述如下：

1. 将待排序的数组调整为最大堆，此时未排序的长度

   N

   为数组的长度，调整的过程就是倒序将数组的前

   N/2

   个元素下沉的过程，每次下沉都会将较大的元素带到上面，最终将数组变为最大堆；

2. 弹出最大堆的堆顶元素并将其移动到数组的最后面，将原本最后面的元素放到堆顶，然后将未排序的长度

   N

   – 1，调整数组的前

   N

   个元素为最大堆；

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

实现代码

package com.zhiyiyo.collection.sort;import java.util.Arrays;public class HeapSort extends BaseSort {@Overridepublic void sort(Comparable[] array) {int N = array.length;// 创建最大堆for (int i = N / 2; i >= 0; i--) {sink(array, i, N);}// 就地排序while (N > 0) {// 将最大的元素移动到数组的尾部，同时将未排序的长度-1swap(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 {@Testpublic 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]，以上~