如何使用C++實現堆排序算法

一、什麼是堆排序算法

堆排序算法是一種基於完全二叉樹的排序算法，它指定了一個最大/最小堆的概念，通過不斷將根節點移動到數組的末尾，並對餘下的元素重建堆，最後達到排序的目的。堆排序算法的時間複雜度為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兩個函數，便可以對序列進行排序。在實際應用中，還可以通過堆化方式構建初始堆，進一步提高堆排序的效率。