Python 算法基础篇：堆排序和计数排序

def heapify(arr, n, i):
    largest = i        # 初始化最大元素的索引
    left_child = 2 * i + 1
    right_child = 2 * i + 2

    # 判断左子节点是否大于根节点
    if left_child < n and arr[i] < arr[left_child]:
        largest = left_child

    # 判断右子节点是否大于根节点
    if right_child < n and arr[largest] < arr[right_child]:
        largest = right_child

    # 如果最大元素不是根节点，则交换它们，并继续堆化
    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 = [64, 34, 25, 12, 22, 11, 90]
heap_sort(arr)
print("堆排序结果：", arr)

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    # 统计列表中每个元素的出现次数
    count = [0] * range_val
    for num in arr:
        count[num - min_val] += 1

    # 根据统计结果构建有序列表
    sorted_arr = []
    for i in range(range_val):
        for j in range(count[i]):
            sorted_arr.append(i + min_val)

    return sorted_arr

# 测试计数排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = counting_sort(arr)
print("计数排序结果：", sorted_arr)