排序算法-堆排序

参考：

1. Java排序算法(五)：堆排序
2. 【算法与数据结构】图说堆排序
3. 【数据结构】排序算法：希尔、归并、快速、堆排序

0. 完全二叉树性质

1. 在完全二叉树中，所有大于n/2的节点都是叶子节点；
2. 如果2i+1<n,则左孩子节点序号为2i+1；否则i无左孩子；
   如果2i+2<n,则右孩子节点序号为2i+2；否则i无有孩子；

1. 算法说明

堆排序是对简单排序的一种改进；

• 简单排序的缺点：
  简单排序要从n条记录中找出一个最小的记录，需要比较n-1次。
  但是这样的操作并没有把每一趟的比较结果都保存下来，在后一趟比较过程中，有许多比较在前一趟中已经做过了，但由于前一趟并未保存这些比较结果，所以后一趟排序又重复执行了这些比较操作，因而比较次数较多。

• 堆排序是一颗完全二叉树。

  • 大顶堆：每个节点都>=其左右孩子节点的值；
  • 小顶堆：每个节点都<=其左右孩子节点的值；

大顶堆和小顶堆

2. 算法思想

• 步骤：
  将待排序的序列构造成一个大顶堆。此时，整个序列的最大值，就是堆顶的跟节点。将它移走（和堆数组的最后元素交换，此时末尾的元素就是最大值 ），将剩余的n-1个元素重新构建成一个堆，就会得到n个元素中的次大值。如此反复，就能得到一个有序序列。

• 问题：

  1. 如何将一个无序序列构建成一个堆？
  2. 如何在输出堆顶元素之后，调整剩余的元素成为一个新堆？

3. java代码实现

堆排序 建堆/调整堆过程 测试方法 结果

4.时间复杂度

• O(nlogn)
• 堆排序是不稳定排序；