# 堆排序（Heap Sort）

URL: https://caijiao.org/sort/7-heap-sort
Source: docs/sort/7-heap-sort.md
Description: 堆排序是一种基于堆数据结构的高效排序算法，具有 O(n log n) 的时间复杂度。本文提供 JavaScript、Python、C++、Java、PHP、Go 多语言实现及详细解释。

堆排序是一种利用**堆这种数据结构**设计的高效排序算法。它通常用**最大堆**来实现升序排序，先构建一个大顶堆，然后不断取出堆顶元素与末尾元素交换，再重新调整堆。

堆排序的**时间复杂度为 O(n log n)**，**空间复杂度为 O(1)**，且**不稳定**，适用于对空间要求严格的排序任务。

## 📌 算法原理解释

堆排序的关键步骤如下：

1. **构建最大堆**：将数组调整为满足最大堆性质（父节点 ≥ 子节点）；
2. **交换根节点与末尾元素**；
3. **重新调整堆结构**（堆化）；
4. 重复步骤 2 和 3，直到堆的大小为 1。

**示意过程**（升序）：

- 初始：`[4, 10, 3, 5, 1]` → 构建最大堆 → `[10, 5, 3, 4, 1]`
- 交换最大值和末尾：`[1, 5, 3, 4, 10]`
- 调整剩余堆 → `[5, 4, 3, 1, 10]`，以此类推...

## 💻 多语言代码实现


// JavaScript 堆排序
function heapSort(arr) {
  const n = arr.length;

  function heapify(i, heapSize) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;

    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(largest, heapSize);
    }
  }

  // 构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(i, n);

  // 依次取出堆顶元素
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(0, i);
  }

  return arr;
}
````

```python
# Python 堆排序
def heap_sort(arr):
    def heapify(n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2

        if l < n and arr[l] > arr[largest]:
            largest = l
        if r < n and arr[r] > arr[largest]:
            largest = r

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(n, largest)

    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(i, 0)

    return arr
```

```cpp
// C++ 堆排序
#include <vector>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2 * i + 1, 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) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}
```

```java
// Java 堆排序
public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2 * i + 1, 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) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}
```

```php
<?php
// PHP 堆排序
function heapSort(array $arr): array {
    $n = count($arr);

    function heapify(&$arr, $n, $i) {
        $largest = $i;
        $left = 2 * $i + 1;
        $right = 2 * $i + 2;

        if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
        if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;

        if ($largest !== $i) {
            [$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
            heapify($arr, $n, $largest);
        }
    }

    for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) heapify($arr, $n, $i);
    for ($i = $n - 1; $i > 0; $i--) {
        [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
        heapify($arr, $i, 0);
    }

    return $arr;
}
?>
```

```go
// Go 堆排序
package main

func heapSort(arr []int) []int {
    n := len(arr)

    var heapify func(int, int)
    heapify = func(n, i int) {
        largest := i
        l, r := 2*i+1, 2*i+2

        if l < n && arr[l] > arr[largest] {
            largest = l
        }
        if r < n && arr[r] > arr[largest] {
            largest = r
        }

        if largest != i {
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(n, largest)
        }
    }

    for i := n/2 - 1; i >= 0; i-- {
        heapify(n, i)
    }

    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(i, 0)
    }

    return arr
}
```


## ✅ 算法特点与总结

| 属性     | 描述         |
| ------ | ---------- |
| 时间复杂度  | O(n log n) |
| 空间复杂度  | O(1)（原地排序） |
| 稳定性    | ❌ 不稳定      |
| 是否原地排序 | ✅ 是        |

> 📌 提示：堆排序适合内存受限的场合，不适合对排序稳定性有要求的应用。