堆排序是一种基于二叉堆的排序算法，它的时间复杂度为O(nlogn)，空间复杂度为O(1)。
堆排序的基本思想是：先将待排序的序列构建成一个大根堆（或小根堆），然后不断取出堆顶元素，将其放到已排序的序列中，并调整剩余元素构成的堆，重复这个过程直到所有元素都被取出。
下面是堆排序的具体实现：
1.构建大根堆
从最后一个非叶子节点开始，对每个节点进行下沉操作，使其满足大根堆的性质。
void adjustHeap(vector& nums, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && nums[left] > nums[largest]) {
largest = left;
}
if (right < len && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums[i], nums[largest]);
adjustHeap(nums, largest, len);
}
}
void buildHeap(vector& nums) {
int len = nums.size();
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(nums, i, len);
}
}
2.堆排序
每次将堆顶元素取出，放到已排序的序列中，然后调整剩余元素构成的堆。
void heapSort(vector& nums) {
int len = nums.size();
buildHeap(nums);
for (int i = len - 1; i >= 0; i--) {
swap(nums[0], nums[i]);
adjustHeap(nums, 0, i);
}
}
完整代码如下：
#include
#include
using namespace std;
void adjustHeap(vector& nums, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && nums[left] > nums[largest]) {
largest = left;
}
if (right < len && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums[i], nums[largest]);
adjustHeap(nums, largest, len);
}
}
void buildHeap(vector& nums) {
int len = nums.size();
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(nums, i, len);
}
}
void heapSort(vector& nums) {
int len = nums.size();
buildHeap(nums);
for (int i = len - 1; i >= 0; i--) {
swap(nums[0], nums[i]);
adjustHeap(nums, 0, i);
}
}
int main() {
vector nums = { 6, 5, 3, 1, 8, 7, 2, 4 };
heapSort(nums);
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
return 0;
