堆排序（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]
1.取出根节点： 取出堆的根节点元素，即 9，并将其放入已排序的部分。
2.重建堆： 删除根节点后，重新调整堆结构，确保其满足最大堆的性质。
剩余堆： [5, 4, 2, 3]
1.重复操作： 重复步骤2和步骤3，直到堆中的元素为空。已经取出的元素会构成已排序部分。这个过程得到了一个升序排列的已排序数组 [2, 3, 4, 5, 9]。
堆排序的时间复杂度
堆排序的时间复杂度保持在O(n*log(n))，其中n是数组的长度。这使得它在处理大型数据集时具有出色的性能。堆排序不需要额外的存储空间，因此具有O(1)的空间复杂度。
堆排序的稳定性取决于堆的性质。如果使用最大堆来进行排序，相同元素的相对顺序可能会发生变化，因此它通常是不稳定的排序算法。
示例代码
以下是堆排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 堆排序
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 堆排序
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 堆排序
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 语言 堆排序
#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; }
以上示例代码展示了不同编程语言中的堆排序算法实现。这些示例帮助你理解堆排序的工作原理，并提供了可供参考和使用的代码示例。堆排序是一种高效且稳定的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。
