堆排序（Heap Sort）

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

堆排序的时间复杂度为 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

// 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)（原地排序）
稳定性	❌ 不稳定
是否原地排序	✅ 是

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