文章转自这里传送门，写的太棒了，值得学习和推广
1.基础知识
堆排序，就是以堆的形式去排序。
关于堆 则需要先了解 完全二叉树和满二叉树
满二叉树在一棵二叉树中，如果所有分支节点都存在左子树和有子树，并且所有叶子都在同一层上，这样的二叉树称之为满二叉树
满二叉树
`完全二叉树` 对一棵具有n个节点的二叉树 `按层序编号`，如果编号为 i (1 ≤ i ≤ n)的结点与同样深度的满二叉树中编号为 i 的结点 在二叉树中位置完全相同，则这棵二叉树成为完全二叉树
也就是必须具备以下两点
1. 除了根层和最后一层之外，第N层的元素个数都必须是2的N次方；第一层2个元素，第二层4个，第三层8个，以此类推
2. 最后一行的元素，都要紧贴在左边， 换句话说：每一行元素都从左边开始安放，两个元素之间不能有空闲
完全二叉树
完全二叉树与堆的关系：
假设有一颗完全二叉树，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值，这样层层递推，就是根节点的值最小，这样的树，称之为小根堆。
同理，对于任意一个子节点来说，均不大于其父节点的值，层层递推，就是根节点的值最大，这样的树，称之为大根堆
大根堆和小根堆
2.推导过程
给定一个数组 array = [16,7,3,20,17,8] 对其进行堆排序（大根堆）
步骤：1.构建大根堆
a1:假设给定无需序列结构如下
a2：此时我们从最后一个非叶子结点开始（第一个非叶子结点 arr.length / 2-1 = 5/2-1 = 1,也就是下面的6结点，从左至右，从下至上调整）
此处必须注意，我们把6和9比较交换之后，必须考虑9这个结点对于其子节点会不会产生任何影响？ 因为其是叶子结点，所以不加考虑；但是，一定要有这种思维，就很容易理解下面的代码为什么会出现一次非常重要的交换了
a3：找到第二个非叶子结点4，由于[4,9,8]中9最大，4和9交换
这是4和9交换之后，必须考虑9原来所在的下标为1这个结点位置，因为其上的值变了，必须判断对其的两个子结点是否造成了影响。实际上就是判断其作为根结点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判断清除，构建成大根堆
这时，交换导致了子树 [4，5，6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6
牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判断一下，这里 4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为止
此时，我们就将一个无序序列构建成了一个大根堆
步骤2：将堆顶元素与末尾元素进行交换，使末尾元素最大。 然后继续调整前面N-1个元素成大根堆，再将堆顶元素与与N-1的末尾元素交换，得到第二大元素。如此反复，直到堆顶。
a. 将堆顶元素9和末尾元素4进行交换
这里所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的结点个数了。
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
d.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
3.代码实现
void sort(int arr[], int length) {
for (int i = length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, length);
}
// 建堆结束开始排序逻辑
for (int j = length - 1; j > 0; j--) {
swap(arr, 0, j);
adjustHeap(arr, 0, j);
}
}
void adjustHeap(int array[], int i, int length) {
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
// 在两个子节点都有的情况下，先比较两个子节点，让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) {
k++;
}
// 如果发现子节点更大，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，判断以子节点为根的子树会不会受到影响
i = k;
} else {
break;
}
}
}
void swap(int arr[], int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
#prage mark - 使用
int arr[] = {2,1,4,3,6,5,8,7};
int length = sizeof(arr) /sizeof(int);
sort(arr,length);
for (int i = 0; i< length; i++) {
printf("%d,",arr[i]);
}
输出：1,2,3,4,5,6,7,8,
网友评论