TypeScript 陣列的堆排序(heapSort)

堆排序(heapSort)是一種演算法，它利用了堆積的特性，將資料集合中的元素進行排序。堆排序是一種不穩定的排序演算法，它的時間複雜度為O(nlogn)。在TypeScript中，可以使用堆排序來對陣列進行排序。

堆排序的步驟

堆排序的步驟如下：

1. 將資料集合中的元素放入堆積中。
2. 將堆積的根節點與最後一個節點交換，然後將堆積的大小減1，這樣最後一個節點就是最大的元素。
3. 重新調整堆積，使其滿足堆積的性質。
4. 重複步驟2和步驟3，直到堆積的大小為1。

TypeScript 中的堆排序程式碼

以下是TypeScript中的堆排序程式碼：

// 將資料集合中的元素放入堆積中
function heapify(arr: number[], n: number, i: number): void {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

    // 如果左子節點比根節點大，則將最大值更新為左子節點
    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    // 如果右子節點比根節點大，則將最大值更新為右子節點
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    // 如果最大值不等於根節點，則將根節點和最大值交換
    if (largest != i) {
        let temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 交換後，重新調整堆積
        heapify(arr, n, largest);
    }
}

// 堆排序
function heapSort(arr: number[]): void {
    let n = arr.length;

    // 將資料集合中的元素放入堆積中
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 將堆積的根節點與最後一個節點交換，然後將堆積的大小減1
    for (let i = n - 1; i > 0; i--) {
        let temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新調整堆積
        heapify(arr, i, 0);
    }
}

// 測試
let arr = [3, 5, 2, 4, 1];
heapSort(arr);
console.log(arr); // [1, 2, 3, 4, 5]

在上面的程式碼中，我們首先使用heapify()函數將資料集合中的元素放入堆積中，然後使用heapSort()函數對堆積進行排序。

堆排序的優點

堆排序有以下優點：

• 時間複雜度低：堆排序的時間複雜度為O(nlogn)，比起其他排序演算法的時間複雜度要低。
• 不需要額外的記憶體空間：堆排序不需要額外的記憶體空間，它只需要一個輔助變數來交換元素。
• 穩定性：堆排序是一種不穩定的排序演算法。

總結

堆排序是一種演算法，它利用了堆積的特性，將資料集合中的元素進行排序。在TypeScript中，可以使用堆排序來對陣列進行排序。堆排序的時間複雜度為O(nlogn)，比起其他排序演算法的時間複雜度要低，而且它不需要額外的記憶體空間，只需要一個輔助變數來交換元素。