C++实现堆排序详解及代码示例

堆排序是一种高效的排序算法，它利用了二叉堆数据结构来完成排序过程。该算法的核心思想是先将待排序的元素构建成一个大顶堆或小顶堆（大顶堆中父节点的值总是大于或等于子节点，小顶堆则相反），然后将堆顶元素（即当前未排序部分的最大或最小值）与最后一个元素交换，这样就确保了最后一个元素已经是有序的。接着，对剩余的元素重新调整堆结构，使其满足堆的性质，然后重复这个过程，直到整个序列有序。 在C++中，堆排序的实现步骤如下： 1. 定义`heapify`函数： - 接收一个整数数组`arr`，数组长度`n`，以及当前处理的元素下标`i`。 - 初始化`largest`为`i`，表示当前认为的最大元素。 - 计算左子节点和右子节点的下标，分别是`left = 2 * i + 1`和`right = 2 * i + 2`。 - 检查左子节点和右子节点是否存在且大于当前最大元素，如果条件成立，更新`largest`。 - 如果`largest`的值不等于`i`，说明需要交换`arr[i]`和`arr[largest]`，然后对子节点进行递归的`heapify`调整，确保子树保持堆的性质。 2. `heapSort`函数实现： - 从数组的最后一个非叶子节点（`n / 2 - 1`）开始，调用`heapify`函数对每个节点进行堆化操作，以确保整个数组上半部分形成一个大顶堆。 - 接着，从最后一个元素开始（`n - 1`），与堆顶元素（即`arr[0]`）交换位置，然后只保留剩余部分并对新的堆顶元素进行`heapify`，重复这个过程直到只剩一个元素，排序完成。 3. `main`函数示例： - 创建一个包含整数的数组`arr`，例如`{12, 11, 13, 5, 6, 7}`。 - 计算数组长度`n`，这里是6。 - 调用`heapSort(arr, n)`对数组进行排序。 - 输出排序后的数组，输出结果为`{5, 6, 7, 11, 12, 13}`。 通过这段C++代码，我们可以看到堆排序算法的具体实现细节，包括如何构建堆、维护堆的性质以及如何逐步完成排序过程。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，适合对大规模数据进行排序。