C++堆排序詳解

一、堆排序簡介

堆排序是一種基於比較的排序算法，其時間複雜度為O(n log n)。它的基本思想是將待排序的序列構造成一個堆，然後依次取出堆頂元素（最大或最小值），並將剩餘待排序元素重新調整為堆。

堆是一種特殊的樹形數據結構，它通常用數組來實現。堆滿足以下兩個條件：

• 任意節點的值都不大於（或不小於）其左右兒子節點的值，稱為大根堆（或小根堆）
• 堆總是一棵完全二叉樹

二、堆排序過程

堆排序的過程可以分為兩個階段：

1、構建堆

首先將待排序的序列構建成一個大根堆（也可以是小根堆），具體過程如下：

• 從最後一個非葉子節點（即len/2-1）開始，依次將每個節點和其子節點進行比較，如果節點值小於其子節點值，則將其與最大值節點進行交換
• 交換後，被交換的節點位置變為其子節點位置，重複上述過程，直到所有節點都被交換到最後一層為止
• 構建好的堆就是一個符合大根堆或小根堆條件的序列

2、排序

接下來，我們需要將堆頂元素（最大或最小值）取出，然後將剩餘待排序元素重新構建堆，依次進行如下操作：

• 將堆頂元素與最後一個元素交換，最後一個元素為已排序的數據，堆大小減一
• 將剩餘待排序元素重新構建堆

重複以上操作，直到堆中只剩下一個元素，排序完成。

三、C++堆排序代碼

#include <iostream>
using namespace std;

// 建立大根堆
void adjustHeap(int arr[], int len, int i) {
    int j = i;
    // 左子節點
    int left = 2 * i + 1;
    // 右子節點
    int right = 2 * i + 2;
    // 找到最大值
    if (left < len && arr[left] > arr[j]) {
        j = left;
    }
    if (right < len && arr[right] > arr[j]) {
        j = right;
    }
    // 如果當前節點已經是最大值，退出遞歸
    if (j != i) {
        swap(arr[i], arr[j]);
        adjustHeap(arr, len, j);
    }
}

// 堆排序
void heapSort(int arr[], int len) {
    // 構建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    // 排序
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        adjustHeap(arr, i, 0);
    }
}

int main() {
    int arr[] = {9, 2, 4, 1, 3, 7, 8, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, len);
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

四、堆排序優化

以上代碼是最基本的堆排序算法，但是我們可以通過一些優化，進一步提升堆排序的效率。

1、堆化優化

在建堆過程中，我們可以將數組從後往前遍歷，對於每個節點，只需將其與其子節點進行比較，而不必和所有子孫節點都進行比較。這樣可以減少比較次數，提升效率。

// 建立大根堆
void adjustHeap(int arr[], int len, int i) {
    int j = i;
    // 左子節點
    int left = 2 * i + 1;
    // 右子節點
    int right = 2 * i + 2;
    // 找到最大值
    if (left < len && arr[left] > arr[j]) {
        j = left;
    }
    if (right < len && arr[right] > arr[j]) {
        j = right;
    }
    // 如果當前節點已經是最大值或者當前節點沒有子節點，退出遞歸
    if (j != i) {
        swap(arr[i], arr[j]);
        adjustHeap(arr, len, j);
    }
}

2、堆排序優化

在排序過程中，我們可以將堆大小作為參數傳入，不必每次都重新計算。同時，在將堆頂元素與最後一個元素交換位置後，僅需對根節點進行堆化，可以減少一半的比較次數。

// 堆排序
void heapSort(int arr[], int len) {
    // 構建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    // 排序
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        adjustHeap(arr, i, 0);
    }
}

五、總結

堆排序是一種高效的排序算法，通過構建堆結構，可以使排序過程的時間複雜度達到O(n log n)。C++提供了豐富的數據結構和算法庫，可以更方便地實現堆排序，同時優化堆化和排序過程，可以進一步提高算法的效率。