Lwaxx的博客

十大排序算法（六） - 堆排序算法

发表于 更新于 分类于 ， 阅读次数： Valine：

堆排序（Heap Sort）是一种高效的、基于堆数据结构的排序算法，它具有稳定性和可预测的性能，适用于各种数据规模。本文将详细介绍堆排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。

堆排序的基本思想

堆排序的核心思想是通过构建一个二叉堆，将待排序的数组转换为一个堆，然后反复从堆中取出最大（或最小）的元素，并将其放入已排序的部分。具体步骤如下：

  1. 构建堆： 将待排序的数组视为一个完全二叉树，并将其调整为一个堆，通常是一个最大堆（每个节点的值大于或等于其子节点的值）或最小堆（每个节点的值小于或等于其子节点的值）。
  2. 取出根节点： 从堆中取出根节点元素，它是堆中的最大（或最小）元素。
  3. 重建堆： 删除根节点后，将堆重新调整为合法的堆结构。
  4. 重复操作： 重复步骤2和步骤3，直到堆中的元素为空。已经取出的元素会构成已排序部分。
  5. 返回结果： 最终得到一个完全有序的数组。

堆排序的关键在于构建堆和维护堆的性质，以确保每次取出的元素都是堆中的最大（或最小）元素。这一过程使得堆排序的时间复杂度保持在O(n*log(n))，并且在实际应用中表现出色。

堆排序的示例

让我们通过一个示例来理解堆排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。

  1. 构建堆：首先将数组 [5, 2, 9, 3, 4] 转换为一个最大堆。最大堆的性质是父节点的值大于或等于其子节点的值。
    • 原始数组：[5, 2, 9, 3, 4]
    • 最大堆：[9, 4, 5, 3, 2]
  2. 取出根节点：取出堆的根节点元素，即 9，并将其放入已排序的部分。
  3. 重建堆：删除根节点后，重新调整堆结构，确保其满足最大堆的性质。
    • 剩余堆：[5, 4, 2, 3]
  4. 重复操作：重复步骤2和步骤3，直到堆中的元素为空。已经取出的元素会构成已排序部分。这个过程得到了一个升序排列的已排序数组 [2, 3, 4, 5, 9]。

堆排序的时间复杂度

堆排序的时间复杂度保持在O(n*log(n))，其中n是数组的长度。这使得它在处理大型数据集时具有出色的性能。堆排序不需要额外的存储空间，因此具有O(1)的空间复杂度。

堆排序的稳定性取决于堆的性质。如果使用最大堆来进行排序，相同元素的相对顺序可能会发生变化，因此它通常是不稳定的排序算法。

示例代码

以下是堆排序的示例代码，分别使用Python、Go、Java和C语言编写。

Python 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

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

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个取出堆中的元素并排序
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [5, 2, 9, 3, 4]
heap_sort(arr)
print("排序后的数组:", arr)

Go 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package main

import "fmt"

func heapify(arr []int, n int, i int) {
    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)
    }
}

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

    // 构建最大堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // 逐个取出堆中的元素并排序
    for i := n - 1; i > 0; i-- {
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    }
}

func main() {
    arr := []int{5, 2, 9, 3, 4}
    heapSort(arr)
    fmt.Println("排序后的数组:", arr)
}

Java 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Arrays;

public class HeapSort {
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    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);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 4};
        heapSort(arr);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}

C 语言 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

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

        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 构建最大堆
    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);
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上示例代码展示了不同编程语言中的堆排序算法实现。这些示例帮助你理解堆排序的工作原理，并提供了可供参考和使用的代码示例。堆排序是一种高效且稳定的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。