堆排序是一种高效的排序算法,它利用了二叉堆数据结构来完成排序过程。该算法的核心思想是先将待排序的元素构建成一个大顶堆或小顶堆(大顶堆中父节点的值总是大于或等于子节点,小顶堆则相反),然后将堆顶元素(即当前未排序部分的最大或最小值)与最后一个元素交换,这样就确保了最后一个元素已经是有序的。接着,对剩余的元素重新调整堆结构,使其满足堆的性质,然后重复这个过程,直到整个序列有序。
在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),适合对大规模数据进行排序。