如何使用C++中的堆排序演算法

如何使用C 中的堆排序演算法

堆排序是一種常用的排序演算法，它利用堆的性質進行排序。堆排序分為兩個步驟：建堆和排序。在本文中，我們將學習如何使用C 語言實作堆排序演算法，並給出具體的程式碼範例。

1. 堆的定義和性質
   堆是一個完全二元樹，可以分成最大堆和最小堆兩種。最大堆的任意節點的值都大於或等於其子節點的值，最小堆的任意節點的值都小於或等於其子節點的值。在堆排序演算法中，我們通常使用最大堆。

堆的實作可以使用陣列來表示，陣列的下標可以表示堆中的節點編號。對於任意節點i，它的父節點為(i-1)/2，左子節點為2i 1，右子節點為2i 2。

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);
    }
}

3. #排序演算法
   建堆完成後，我們可以進行排序操作，排序的想法是每次取出堆頂元素，將其與堆尾元素交換，然後將剩餘的部分重新進行下沉操作。

以下是堆排序演算法的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);
    }
}

4. #範例和測試
   下面是一個使用堆排序演算法的範例和測試：

#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中文網其他相關文章！