堆排序（Heap Sort）是一种高效的、基于堆数据结构的排序算法，它具有稳定性和可预测的性能，适用于各种数据规模。本文将详细介绍堆排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
堆排序的基本思想
堆排序的核心思想是通过构建一个二叉堆，将待排序的数组转换为一个堆，然后反复从堆中取出最大（或最小）的元素，并将其放入已排序的部分。具体步骤如下：
- 构建堆： 将待排序的数组视为一个完全二叉树，并将其调整为一个堆，通常是一个最大堆（每个节点的值大于或等于其子节点的值）或最小堆（每个节点的值小于或等于其子节点的值）。
- 取出根节点： 从堆中取出根节点元素，它是堆中的最大（或最小）元素。
- 重建堆： 删除根节点后，将堆重新调整为合法的堆结构。
- 重复操作： 重复步骤2和步骤3，直到堆中的元素为空。已经取出的元素会构成已排序部分。
- 返回结果： 最终得到一个完全有序的数组。
堆排序的关键在于构建堆和维护堆的性质，以确保每次取出的元素都是堆中的最大（或最小）元素。这一过程使得堆排序的时间复杂度保持在O(n*log(n))，并且在实际应用中表现出色。
堆排序的示例
让我们通过一个示例来理解堆排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。
- 构建堆： 首先将数组
[5, 2, 9, 3, 4]转换为一个最大堆。最大堆的性质是父节点的值大于或等于其子节点的值。
原始数组： [5, 2, 9, 3, 4]
最大堆： [9, 4, 5, 3, 2]- 取出根节点： 取出堆的根节点元素，即
9，并将其放入已排序的部分。 - 重建堆： 删除根节点后，重新调整堆结构，确保其满足最大堆的性质。
剩余堆： [5, 4, 2, 3]- 重复操作： 重复步骤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;
}以上示例代码展示了不同编程语言中的堆排序算法实现。这些示例帮助你理解堆排序的工作原理，并提供了可供参考和使用的代码示例。堆排序是一种高效且稳定的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。