排序算法实现-堆排序(Java版本)（堆排序实现代码）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

其大致比较执行图为：

• 定义

堆排序其实是利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

如：

n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：

(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

• 堆数据结构分析
  

1. 高度：堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）。

2. 堆节点的访问：通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：父节点i的左子节点在位置(2*i+1);父节点i的右子节点在位置(2*i+2);子节点i的父节点在位置floor((i-1)/2);

3. 堆的操作：在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。创建最大堆（Build_Max_Heap）：将堆所有数据重新排序堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆的基本排序步骤为：

• Java实现源码分析

首先创建一个方法表示堆排序，参数为待排序数组

1. 在排序之前，我们首先要对当前数组建立一个最大堆或者最小堆

2. 然后迭代一次迭代前（n-1）个数，继续奖励最大堆或者最小堆，依次迭代，直到剩下长度为1

那么如何建立最大堆呢(最小堆相反比较即可)，源码如下：

因为只需要对非叶子节点做最大堆构建，所以建立最大堆的cao做实际上是[0, n/2]之间的节点。

1. 该方法为对序号为i的节点做最大堆的构建，那么该节点的左子节点为：i*2-1, 右子节点为：i*2

2. 需要检验左右子节点是否存在。

3. 当发现构造的当前堆的根节点发生变更时，需要再次对其父节点做最大堆的重新构造。
   

我们可以发现，堆算法巧妙的运用了数组和二叉树数据结构关系以及堆数据结构的性质来实现的。只要你懂得最大堆、最小堆的性质，以及如何构建一个最大堆和最小堆，那么该算法应该很快能实现

• 算法分析

1. 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

2. 平均性能：O(N*logN)。

3. 其他性能：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）.

4. 它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化）

完整代码可参考: https://zhuanlan.zhihu.com/p/25566353

如果这对你有用，粉我吧，每天都有干货哦

历史相关内容

• 排序算法 - 冒泡排序

• 排序算法 - 插入排序

• 排序算法 - 桶排序

• 排序算法 - 希尔排序