排序 - 堆排序

文章转自这里传送门，写的太棒了，值得学习和推广

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,