C++堆排序原理与示例代码解析

堆排序是一种比较知名的排序算法，属于选择排序的一种。它利用二叉堆这一数据结构的特性来进行排序。在C++中，堆排序可以使用STL（标准模板库）中的堆算法来实现。堆排序的过程可以分为两个步骤：建立堆和堆调整，以实现数据的排序。 首先，我们需要了解什么是二叉堆。二叉堆是一种特殊的完全二叉树，它可以分为两类：最大堆和最小堆。在最大堆中，任何一个父节点的值都大于或等于它的子节点，这就保证了根节点是所有节点中的最大值；而在最小堆中，任何一个父节点的值都小于或等于它的子节点，根节点是所有节点中的最小值。由于堆是一种特殊的树形数据结构，因此它能很自然地被存储在数组中。 堆排序的实现原理主要包括以下几个步骤： 1. 建立堆：将无序的序列调整为堆结构。这一步是通过一系列的下沉操作来完成的，目的是保证每个非叶子节点都大于或等于它的子节点（最大堆），从而确保堆顶元素是整个序列中的最大值或最小值。 2. 堆调整：将堆顶元素（当前最大或最小）与堆中的最后一个元素交换，并去掉最后一个元素（因为已经放在了堆顶），这样堆的大小就减小了1。然后对剩余的堆结构进行下沉操作，重新建立起最大堆或最小堆的性质。这样，每次都能将当前的最大值或最小值移动到堆的末尾，并保持堆的其他部分符合堆的定义。 3. 重复执行堆调整，直到堆的大小为1时，整个序列就完成了排序。 下面是一个C++中堆排序的示例代码，展示了如何通过手动编码实现堆排序算法： ```cpp #include <iostream> #include <vector> void adjustHeap(std::vector<int>& vec, int start, int end) { int dad = start; int son = dad * 2 + 1; // 建立子节点索引 while (son <= end) { // 如果子节点索引在范围内才进行比较 // 如果有右孩子节点，并且右孩子的值大于左孩子的值，则定位到右孩子 if (son + 1 <= end && vec[son] < vec[son + 1]) { son++; } // 如果父节点的值已经大于子节点的值，则直接结束 if (vec[dad] > vec[son]) { return; } else { // 否则交换父子内容再继续向下筛选 std::swap(vec[dad], vec[son]); dad = son; son = dad * 2 + 1; } } } void heapSort(std::vector<int>& vec) { int len = vec.size(); // 从最后一个非叶子节点开始向上构建最大堆 for (int i = len / 2 - 1; i >= 0; --i) { adjustHeap(vec, i, len - 1); } // 一个个从堆顶取出元素，进行堆调整 for (int i = len - 1; i > 0; --i) { std::swap(vec[0], vec[i]); // 将当前最大值放到数组末尾 adjustHeap(vec, 0, i - 1); // 重新调整堆，排除已经放置好的最大值 } } int main() { std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; heapSort(vec); for (auto e : vec) { std::cout << e << ' '; } std::cout << std::endl; return 0; } ``` 这段代码首先定义了一个`adjustHeap`函数用于调整堆结构，然后定义了`heapSort`函数来执行堆排序。`heapSort`函数先将给定的数组调整为最大堆，然后通过不断地将最大元素移动到数组末尾，并对剩余元素调整为最大堆，从而完成整个排序过程。 由于堆排序是一种不稳定的排序算法，它对于相同值的元素可能会改变它们的原始顺序。尽管如此，堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，因此它在处理大数据量时仍然非常高效。堆排序算法特别适合在需要动态数据排序的场景中使用，如优先队列的实现。