排序算法 --- 堆排序
1. 堆排序介绍：
- 堆排序是利用“堆”这种数据结构设计的，也是一种选择排序，时间复杂度为O(nlogn)，属于不稳定排序。
- 堆，其实就是具有某些特征的完全二叉树。特点就是：每个节点的值都大于其左右孩子节点的值，这样的叫大顶堆；反之叫小顶堆。
大顶堆
如果我们以图中黑色数字作为索引将值依次存到数组里，那么数组就是：
50, 45, 40, 20, 26, 35, 30, 10, 15可以发现，arr[i] > arr[2*i + 1]，arr[i] > arr[2*i + 2]。
在用堆排序的时候，如果要升序，那就使用大顶堆，如果要降序，那就使用小顶堆。··
2. 排序思想：
- 将待排序列构造成一个最大堆。不需要真正地构建二叉树，之前说了二叉树的顺序存储，这里就派上用场了；
- 此时，整个序列的最大值就是堆顶的根节点；
- 将堆顶元素与末尾元素进行交换，此时末尾元素就是最大值；
- 将剩余的(n - 1)个元素，重新构造成一个堆，如此反复执行……
3. 代码实现：
首先写个方法，将树调整成大顶堆，具体步骤看代码注释：
/**
* 把以index为父节点的子树调整成大顶堆
* @param arr 数组
* @param index 非叶子节点的索引
* @param length 对多少个元素进行调整
*/
private static void buildHeap(int[] arr, int index, int length) {
// 保存index对应的值，其实就是要调整子树的父节点的值
int temp = arr[index];
// 开始调整，i就是index节点的左子节点
for (int i=(index * 2 + 1); i<length; i = (i * 2 + 1)) {
// 如果左子节点小于右子节点，那就让i指到右子节点
if (i + 1 < length && arr[i] < arr[i+1]) {
i++;
}
// 经过上面操作，arr[i]就是最大的子节点
if (arr[i] > temp) {
// 如果最大子节点的值比父节点更大，就把这个子节点的值赋给父节点
arr[index] = arr[i];
// 然后就以刚才那个最大子节点为父节点，再循环进行调整
index = i;
} else {
break;
}
}
// 循环结束，就是调整结束，要把刚才保存的父节点的值赋给当前节点，这才完成了父节点与子节点值的交换
arr[index] = temp;
}然后就可以写排序方法了，首先调用一次调整大顶堆的方法，然后将堆顶元素放到最后，此时最后那个元素就是最大的了，然后再进行调整，就可以少调整一个数了，具体代码如下：
public static void sort(int[] arr) {
// 遍历数组，找到非叶子节点，对以非叶子节点为父节点的子树进行调整
// (arr.length / 2 - 1)就可以找到完全二叉树的最后一个非叶子节点
for(int i=(arr.length / 2 - 1); i>=0; i--) {
buildHeap(arr, i, arr.length);
}
// 调整成大顶堆后，让堆顶元素与末尾元素进行交换，此时末尾元素就是最大值
int temp;
for(int j=arr.length-1; j>0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
// 交换完后，将剩余的(n-1)个元素再调整成大顶堆
buildHeap(arr, 0, j);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读