🤔 堆排序

1. 从0到n建堆，父节点序数为
左右孩子
用while往上找
为什么要先用非叶子结点构建堆，而不是从整个数组直接构建？
使用非叶子节点构建堆而不是从整个数组直接构建的原因在于效率和算法的逻辑结构。
1. 效率：从最后一个非叶子节点开始构建堆可以减少不必要的比较和交换操作。由于叶子节点（数组的最后几个元素）没有子节点，它们自然形成最大堆的一部分（在最大堆中，所有叶子节点都是最大元素）。因此，从最后一个非叶子节点开始，向上逐层调整，可以更快地构建整个堆。
2. 完全二叉树的性质：在完全二叉树表示的堆中，任何非叶子节点至少有一个子节点。这意味着从最后一个非叶子节点开始，可以确保每个节点在调整过程中都至少有一个子节点可以比较。如果从根节点开始，那么在构建堆的过程中，很多节点将没有子节点，这将导致算法效率降低。
3. 递归调整：从最后一个非叶子节点开始，可以利用递归的方式进行堆的调整。每次调用heapify函数时，都会对当前节点及其子节点进行调整，确保它们满足最大堆的性质。这种方法可以自然地应用到任何子树的调整中，而不需要特别处理叶子节点。
4. 避免重复工作：如果从根节点开始构建堆，那么在调整根节点时，可能需要对整个树进行多次调整。而从最后一个非叶子节点开始，可以确保在构建堆的过程中，每个节点只被调整一次，从而避免了重复工作。
总结来说，从最后一个非叶子节点开始构建堆是一种更高效、更符合完全二叉树结构特性的方法，它利用了递归调整的便利性，减少了不必要的操作，从而提高了堆排序算法的效率。
结构：
heapify()
heapsort():先建非叶子节点的堆，再插入叶子节点
· 为什么建堆后要对整个堆进行调整？
在堆排序算法中，建堆之后对整个堆进行调整的原因是为了确保整个数组满足最大堆的性质，这是进行有效排序的前提。以下是详细解释：
5. 最大堆的定义：最大堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于其子节点的值。在堆排序中，我们使用最大堆来保证最大的元素位于堆的顶部，从而可以被优先取出。
6. 初始状态：在堆排序开始之前，数组是无序的。虽然我们可能已经通过heapify函数从最后一个非叶子节点开始构建了最大堆，但这只是部分地调整了数组。数组的前半部分（即堆的顶部）可能仍然不符合最大堆的性质。
7. 交换操作：在堆排序的交换步骤中，我们将堆顶元素（最大元素）与数组的最后一个元素交换，然后删除最后一个元素（即完成排序的元素）。这个操作会破坏最大堆的性质，特别是交换后堆顶元素可能不再是最大的。
8. 重新调整：为了修复由于交换操作导致的堆性质破坏，我们需要重新对堆进行调整。这通常是通过调用heapify函数，从交换后的堆顶元素开始向下调整，确保所有子节点都小于或等于父节点。
9. 重复过程：在每次交换操作之后，都需要对堆进行重新调整。这个过程会重复进行，直到所有元素都被排序。
10. 效率：虽然每次交换后都需要重新调整堆，但这种调整是局部的，只需要从交换后的堆顶元素开始，向下调整到叶子节点。这比重新对整个堆进行调整要高效得多。
总结来说，建堆后对整个堆进行调整是为了维护最大堆的性质，确保堆排序算法可以正确地进行元素的排序。这种调整是必要的，因为它允许算法在每次交换最大元素后，都能快速地恢复堆的性质，从而继续进行排序过程。
使用大根堆完成从小到大的排序，是因为在堆排序的过程中，我们首先将数组构建成一个大根堆，这样保证堆顶的元素是数组中的最大值。然后，我们将堆顶元素（最大值）与堆的最后一个元素交换，这样最大值就被移动到了它应该在的位置（数组的末尾）。接着，我们对剩下的元素重新调整堆结构，再次将最大值放到堆顶，然后重复这个过程，直到堆的大小减少到1，此时数组就变成了一个从小到大排序的序列。
下面通过一个具体的例子来说明这个过程：
假设我们有以下数组：[4, 10, 3, 5, 1]
11. 构建大根堆：
• 首先，我们从最后一个非叶子节点开始（即索引为(5-1)/2 = 2的元素，也就是数字3），向下调整堆结构，使得每个父节点的值都大于其子节点的值。
• 调整后的堆可能如下所示（这里只是示意，实际构建堆的过程可能需要多次调整）：[10, 5, 3, 4, 1]（10是堆顶，也就是当前的最大值）
12. 交换堆顶元素与最后一个元素：
• 交换堆顶元素10与最后一个元素1：[1, 5, 3, 4, 10]
• 此时，10已经位于它应该在的位置，数组的末尾。
13. 重新调整堆结构：
• 现在我们对剩下的元素[1, 5, 3, 4]重新构建大根堆。
• 调整后的堆可能如下所示：[5, 4, 3, 1]（5是新的堆顶）
14. 重复上述过程：
• 再次交换堆顶元素5与当前堆的最后一个元素1：[1, 4, 3, 5]
• 对剩下的元素[1, 4, 3]重新构建大根堆：[4, 1, 3]
15. 继续重复，直到堆的大小为1：
• 交换堆顶元素4与堆的最后一个元素3：[3, 1, 4]
• 重新构建堆：[3, 1]
• 交换堆顶元素3与堆的最后一个元素1：[1, 3]
最终，我们得到一个从小到大排序的数组：[1, 3]。
 

📝快速排序

归并排序

两个vector记录，小的记录到nums[k]后++

🤗总结归纳

参考文章