如何使用C 中的堆排序演算法
堆排序是一種常用的排序演算法，它利用堆的性質進行排序。堆排序分為兩個步驟：建堆和排序。在本文中，我們將學習如何使用C 語言實作堆排序演算法，並給出具體的程式碼範例。
堆的實作可以使用陣列來表示，陣列的下標可以表示堆中的節點編號。對於任意節點i，它的父節點為(i-1)/2，左子節點為2i 1，右子節點為2i 2。
下面是建堆演算法的C 程式碼範例：
// 下沉操作，将指定节点下沉到合适的位置
void downAdjust(int arr[], int parent, int length) {
int child = 2 * parent + 1; // 左子节点的下标
int temp = arr[parent]; // 保存要下沉的节点的值
while (child < length) {
// 如果有右子节点，且右子节点的值大于左子节点的值，则选择右子节点
if (child+1 < length && arr[child] < arr[child+1]) {
child++;
}
// 如果父节点的值大于等于子节点的值，则下沉结束
if (temp >= arr[child]) {
break;
}
// 将子节点的值上移，代替父节点
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
// 将要下沉的节点插入合适的位置
arr[parent] = temp;
}
// 建堆算法，将无序数组构建成最大堆
void buildHeap(int arr[], int length) {
// 从最后一个非叶子节点开始，依次进行下沉操作
for (int i = (length-2) / 2; i >= 0; i--) {
downAdjust(arr, i, length);
}
}以下是堆排序演算法的C 程式碼範例：
// 堆排序算法
void heapSort(int arr[], int length) {
// 1. 构建最大堆
buildHeap(arr, length);
// 2. 排序
for (int i = length - 1; i > 0; i--) {
// 将堆顶元素与堆尾元素交换
swap(arr[i], arr[0]);
// 对剩下的部分重新进行下沉操作
downAdjust(arr, 0, i);
}
}#include <iostream>
// 输出数组元素
void printArray(int arr[], int length) {
for (int i = 0; i < length; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
// 主函数
int main() {
int arr[] = {4, 1, 3, 9, 7};
int length = sizeof(arr) / sizeof(int);
std::cout << "排序前的数组：" << std::endl;
printArray(arr, length);
// 使用堆排序算法进行排序
heapSort(arr, length);
std::cout << "排序后的数组：" << std::endl;
printArray(arr, length);
return 0;
}輸出結果為：
排序前的数组： 4 1 3 9 7 排序后的数组： 1 3 4 7 9
透過上述範例和測試，我們可以看到使用C 語言實作的堆排序演算法可以正確地對陣列進行排序。
總結：
本文介紹如何使用C 語言實作堆排序演算法，並給出了具體的程式碼範例。堆排序演算法的核心在於建堆和排序兩個步驟，其中建堆的思路是從最後一個非葉子節點開始進行下沉操作，排序的思路是每次取出堆頂元素，將其與堆尾元素交換，並對剩下的部分重新進行下沉操作。透過實際測試，我們可以驗證堆排序演算法的正確性和穩定性。
以上是如何使用C++中的堆排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
