一、什么是堆排序算法
堆排序算法是一种基于完全二叉树的排序算法，它指定了一个最大/最小堆的概念，通过不断将根节点移动到数组的末尾，并对余下的元素重建堆，最后达到排序的目的。堆排序算法的时间复杂度为O(nlogn)。
二、堆排序算法的实现步骤
1. 构建初始堆：将n个元素构建成初始堆，从最后一个非叶子结点开始，自下而上执行堆调整（maxHeap）。
2. 将堆顶元素放到末尾：交换堆顶元素和序列末尾元素，堆大小减1。
3. 重建堆：对新的堆顶元素进行heapify操作（maxHeap），将其放到正确的位置。
4. 重复上述步骤，直到堆大小为1。
三、C++实现堆排序算法
#include <iostream>
#include <vector>
using namespace std;
// 构建初始堆
void maxHeapify(vector<int>& nums, int heapSize, int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < heapSize && nums[left] > nums[largest]) {
largest = left;
}
if (right < heapSize && nums[right] > nums[largest]) {
largest = right;
}
if (largest != index) {
swap(nums[index], nums[largest]);
maxHeapify(nums, heapSize, largest);
}
}
// 堆排序
void heapSort(vector<int>& nums) {
int n = nums.size();
// 构建初始堆
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(nums, n, i);
}
// 将堆顶元素放到末尾，重建堆
for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]);
maxHeapify(nums, i, 0);
}
}
int main() {
vector<int> nums = {4, 1, 3, 2, 5, 6};
heapSort(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}
四、堆排序算法的优化
堆排序算法可以有许多优化，比如使用最小堆代替最大堆，使用堆内存储的元素下标代替额外空间存储堆元素，使用堆化的方式构建初始堆等等。
其中，使用堆化的方式构建初始堆可以减少时间复杂度，堆化方式有自上而下的堆化和自下而上的堆化。自上而下的堆化相比自下而上的堆化来说，需要更多的swap操作，但在堆偏小的情况下会比较适用。
// 自上而下的堆化
void maxHeapify(vector<int>& nums, int heapSize, int index) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
while (left < heapSize) {
if (nums[left] > nums[largest]) {
largest = left;
}
if (right < heapSize && nums[right] > nums[largest]) {
largest = right;
}
if (largest != index) {
swap(nums[index], nums[largest]);
index = largest;
left = 2 * index + 1;
right = 2 * index + 2;
largest = index;
} else {
break;
}
}
}
五、总结
堆排序算法是一种快速稳定的排序算法，通过构建最大/最小堆的方式对无序序列进行排序。C++实现堆排序只需要实现maxHeapify和heapSort两个函数，便可以对序列进行排序。在实际应用中，还可以通过堆化方式构建初始堆，进一步提高堆排序的效率。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/239104.html
微信扫一扫 
支付宝扫一扫 