堆排序（Heap Sort）

  堆排序是一种利用堆这种数据结构特性实现的排序算法，被认为是一种选择排序。堆排序在排序数据量较大时，性能相对比较优越。

基本思想

  堆排序的核心是堆这种数据结构的特性。堆是什么，堆可以理解成完全二叉树，且堆要求子节点完全小于等于或完全大于等于父节点，也就是说堆只有两种形式：子节点完全小于等于父节点的，被称为大顶堆；子节点完全大于等于父节点的，被称为小顶堆。见图参考，大顶堆小顶堆：

  当然，堆是一种基于树形结构思维特性的运用，在实际使用的时候，根据它的特性，可以将他的元素节点映射到数组中，如图：

  这个数组，从逻辑上是可以描述堆结构的，然后用公式进行补充定义：
  大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
  小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
  其中arr[2i+1]和arr[2i+2]分别表示节点arr[i]的左右子节点。
  基于以上堆的这些特性，堆排序算法的脉络也就很清晰了：
  将待排数据样本构造成一个大顶堆，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾即为最大值；然后将剩余数据元素进行调整，重新构造成一个大顶堆，如此这般依次往复，即可逐次得到次大值；直至最后，排序完成。
  一般实际使用的时候，升序排序，用大顶堆，降序排序，用小顶堆。

## 算法描述
1：将待排数据元素构造成大顶堆；
2：把第一位和最后一位交换，即得出最大值，换至序列尾部；
3：得到最大值后，继续调整剩余数据元素，成为大顶堆；
4：重复步骤2～3，直至堆排序完成。

## 动图演示

代码实现

import java.util.Arrays;

/**
 * @author :Veiking
 * @version :2020年10月15日 说明 :基数排序算法
 */
public class RadixSort {
    /**
     * 基数排序
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        // 求出待排数的最大元素
        int maxItem = arrays[0];
        for (int i = 1; i < arrays.length; i++) {
            if (maxItem < arrays[i]) {
                maxItem = arrays[i];
            }
        }
        // 根据最大元素得出其计算位数
        int size = String.valueOf(maxItem).length();
        // 由于我们是对数字序列进行排序，即准备0~9十个临时数字数组作为容器，用于基数排序
        // 因考虑到极端情况，数组的第二维度长度与数据样本等长，为arrays.length
        int[][] buckets = new int[10][arrays.length];
        // 用于记录bucket数组中每个桶内存的数据的数量
        int[] counts = new int[10];
        // 用于记录每个数比较位数的数值
        int num = 0;
        // 用于记录取的元素需要放的位置
        int index = 0;
        // 根据最大元素位数决定排序的操作次数，记为i，figure则用于计算数据位数值，个十百千万等
        for (int i = 0; i < size; i++) {
            int figure = (int) Math.pow(10, i);
            // 将样本按位数计算规则，入桶
            for (int j = 0; j < arrays.length; j++) {
                num = arrays[j] / figure % 10;// 取当前位数据值
                buckets[num][counts[num]] = arrays[j]; // 待排元素入桶
                counts[num]++; // 值为num的 bucket桶元素数量递加
            }
            // 从buckets中取元素重新放到原arrays数组中
            for (int j = 0; j < counts.length; j++) {
                // 逐个放回
                for (int k = 0; k < counts[j]; k++) {
                    arrays[index] = buckets[j][k];
                    index++;
                }
                counts[j] = 0; // 放空则计数归零
            }
            index = 0; // 一轮操作完毕，初始归零
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[] { 3, 6, 9, 5, 13, 15, 4, 11, 1, 12, 16, 2, 14, 10, 7, 8 };
        System.out.println("样本初始样本数据：" + Arrays.toString(input));
        int[] output = RadixSort.sort(input);
        System.out.println("基数排序结果数据：" + Arrays.toString(output));
    }
}

算法分析

  堆排序算法的基本性能，归纳如下图：

1、 时间复杂度

  我们从上边的代码分析可以发现，堆排序的主要部分，除了刚开始的堆构建，最主要的步骤是遍历排序时每次堆的调整。我们根据堆结构的特性可以得知，这种运用二分策略算法的时间复杂度，一般被认为是O(nlog₂n)，故可以得知，堆排序算法的也可以认为是O(nlog₂n)；我们可以发现，在堆的调整过程中，数据是否有序，其实并不影响堆比较的次数，为了确保堆结构的规则，该对比的那些步骤，是数据是否有序影响不了的，所以堆排序的好坏平均时间复杂度，皆是O(nlog₂n)。

2、 空间复杂度

  看上边的分析可以了解到，堆排序，主要是堆的调整构建，不需要额外的空间，只需要一个临时变量辅助交换即可，故空间复杂度为O(1)。

2、稳定性

  根据构建堆的调整的机制，我们很容易发现，如果有等值元素，谁最先被调至首位，这个是不确定的，也就是说，堆排序前后，等值元素的相对位置也是不确定的，故堆排序也是不稳定的算法。