堆排序

堆排序利用堆这种数据结构来进行排序，分为最大堆和最小堆两种。

概述

堆排序是一种高效的排序算法，时间复杂度为 O(n log n)，空间复杂度为 O(1)。

算法步骤

1. 构建最大堆: 将数组转换为最大堆
2. 提取堆顶元素: 将堆顶元素与最后一个元素交换
3. 调整堆: 对剩余元素重新构建最大堆
4. 重复: 直到所有元素都被提取

实现

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)
    
    return arr

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)

# 示例
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)  # [5, 6, 7, 11, 12, 13]

最小堆排序

def min_heap_sort(arr):
    n = len(arr)
    
    # 构建最小堆
    for i in range(n // 2 - 1, -1, -1):
        min_heapify(arr, n, i)
    
    # 逐个提取元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        min_heapify(arr, i, 0)
    
    return arr

def min_heapify(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        min_heapify(arr, n, smallest)

# 示例
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = min_heap_sort(arr)
print(sorted_arr)  # [13, 12, 11, 7, 6, 5]（降序）

复杂度分析

情况	时间复杂度
平均	O(n log n)
最好	O(n log n)
最坏	O(n log n)

空间复杂度

• O(1)（原地排序）

优化策略

Floyd 堆排序优化

def floyd_heap_sort(arr):
    n = len(arr)
    
    # 构建堆（Floyd 方法）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 提取元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        
        # 优化的堆化过程
        j = 0
        while True:
            left = 2 * j + 1
            right = 2 * j + 2
            
            if left >= i:
                break
            
            if right >= i or arr[left] >= arr[right]:
                max_child = left
            else:
                max_child = right
            
            if arr[j] >= arr[max_child]:
                break
            
            arr[j], arr[max_child] = arr[max_child], arr[j]
            j = max_child
    
    return arr

应用场景

• 需要原地排序的场景
• 嵌入式系统（内存有限）
• 实时系统（时间复杂度稳定）

与其他排序算法对比

算法	平均时间	空间	稳定
堆排序	O(n log n)	O(1)	否
快速排序	O(n log n)	O(log n)	否
归并排序	O(n log n)	O(n)	是