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

#include using namespace std;

// 交换两个元素的值 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

// 构建最大堆 void buildMaxHeap(int arr[], int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; // 左子节点的索引 int right = 2 * i + 2; // 右子节点的索引

// 如果左子节点比根节点大，则更新最大值
if (left < n && arr[left] > arr[largest])
    largest = left;

// 如果右子节点比最大值大，则更新最大值
if (right < n && arr[right] > arr[largest])
    largest = right;

// 如果最大值不是根节点，则交换根节点和最大值，并递归调整子堆
if (largest != i) {
    swap(&arr[i], &arr[largest]);
    buildMaxHeap(arr, n, largest);
}

}

// 堆排序函数 void heapSort(int arr[], int n) { // 构建最大堆，从最后一个非叶节点开始，依次向上调整子堆 for (int i = n / 2 - 1; i >= 0; i--) buildMaxHeap(arr, n, i);

// 依次取出堆顶元素（最大值），将其与最后一个元素交换，并重新构建最大堆
for (int i = n - 1; i >= 0; i--) {
    swap(&arr[0], &arr[i]);
    buildMaxHeap(arr, i, 0);
}

}

// 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; }

int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]);

cout << "原始数组：";
printArray(arr, n);

heapSort(arr, n);

cout << "排序后的数组：";
printArray(arr, n);

return 0;

}

代码解析：

swap函数用于交换两个元素的值。
buildMaxHeap函数用于构建最大堆。首先将当前节点作为最大值，然后比较其左子节点和右子节点的值，如果有比当前最大值更大的节点，则更新最大值。最后，如果最大值不是当前节点，则交换当前节点和最大值，并递归调整子堆。
heapSort函数用于执行堆排序算法。首先构建最大堆，从最后一个非叶节点开始，依次向上调整子堆。然后依次取出堆顶元素（最大值），将其与最后一个元素交换，并重新构建最大堆。重复这个过程直到排序完成。
printArray函数用于打印数组。
main函数中定义了一个测试数组，并调用heapSort函数对其进行排序，然后打印排序后的结果。

堆排序是一种原地、稳定的排序算法，时间复杂度为O(nlogn)。它利用了堆数据结构的特性进行排序，适用于大数据量的排序任务。