堆排序(Heap Sort)

1.什么是堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。沉积是一个近似齐全二叉树的构造,并同时满足沉积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序能够说是一种利用堆的概念来排序的抉择排序。分为两种办法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的均匀工夫复杂度为 (nlogn)。

2.算法步骤

  1. 创立一个堆 H[0……n-1];
  2. 把堆首(最大值)和堆尾调换;
  3. 把堆的尺寸放大 1,并调用 shift_down(0),目标是把新的数组顶端数据调整到相应地位;
  4. 反复步骤 2,直到堆的尺寸为 1。

3.代码实现

    public static void main(String[] args) {        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};        buildSort(arr);        System.out.println(Arrays.toString(arr));    }    private static void buildSort(int[] tree) {        buildHeap(tree);        for (int i = tree.length - 1; i >= 0; i--) {            swap(tree, 0, i);            heapify(tree, 0, i);        }    }    private static void buildHeap(int[] tree) {        int parent = (tree.length / 2) - 1;        for (int i = parent; i >= 0; i--) {            heapify(tree, i, tree.length);        }    }    private static void heapify(int[] tree, int i, int length) {        int leftChild = 2 * i + 1;        int rightChild = 2 * i + 2;        int max = i;        if (leftChild < length && tree[leftChild] > tree[max]) {            max = leftChild;        }        if (rightChild < length && tree[rightChild] > tree[max]) {            max = rightChild;        }        if (max != i) {            swap(tree, max, i);            heapify(tree, max, length);        }    }    private static void swap(int[] tree, int max, int i) {        int temp = tree[max];        tree[max] = tree[i];        tree[i] = temp;    }

4.输入后果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]