数据结构与算法 / 系统课时

堆排序与非比较排序

堆排序与非比较排序

堆排序提供确定的 O(nlog⁡n)O(n\log n) 时间上界,计数排序则在整数键范围较小时突破比较排序的下界。本课通过同一组数据比较两种方法的过程、空间成本和适用条件。

学习目标

  • 说明最大堆建堆、交换与下沉过程
  • 实现堆排序和支持负整数的计数排序
  • 根据数据规模与键范围选择排序方法

两类排序思路

升序堆排序先自底向上构建最大堆,使堆顶保存当前最大值;随后把堆顶与未排序区末尾交换,缩小堆范围,再对新堆顶执行下沉。建堆为 O(n)O(n),整个排序为 O(nlog⁡n)O(n\log n),且数组内原地完成,但远距离交换使它不稳定。

计数排序不比较元素大小,而是统计每个整数键出现的次数,再按键值顺序展开。其复杂度为 O(n+k)O(n+k),其中 kk 是键值范围长度。只有当 kk 与 nn 同量级或足够小时,它才具有明显优势。

堆排序与计数排序机制对比

主示例

python
def heap_sort(values):
    items = values.copy()
    size = len(items)

    def sift_down(index, heap_size):
        while True:
            left = 2 * index + 1
            right = left + 1
            largest = index

            if left < heap_size and items[left] > items[largest]:
                largest = left
            if right < heap_size and items[right] > items[largest]:
                largest = right
            if largest == index:
                return

            items[index], items[largest] = items[largest], items[index]
            index = largest

    # 最后一个非叶子节点是 size // 2 - 1。
    for index in range(size // 2 - 1, -1, -1):
        sift_down(index, size)

    for end in range(size - 1, 0, -1):
        items[0], items[end] = items[end], items[0]
        sift_down(0, end)

    return items

def counting_sort(values):
    if not values:
        return []

    minimum = min(values)
    maximum = max(values)
    counts = [0] * (maximum - minimum + 1)

    # 使用偏移量同时支持负整数和非负整数。
    for value in values:
        counts[value - minimum] += 1

    result = []
    for offset, count in enumerate(counts):
        result.extend([offset + minimum] * count)
    return result

data = [4, -2, 2, 8, 3, 3, 1]
print("堆排序:", heap_sort(data))
print("计数排序:", counting_sort(data))

预期输出:

text
堆排序: [-2, 1, 2, 3, 3, 4, 8]
计数排序: [-2, 1, 2, 3, 3, 4, 8]

选择与边界

堆排序适合需要原地排序、必须保证最坏 O(nlog⁡n)O(n\log n),且不要求稳定性的场景。交换到数组末尾的元素已经有序,后续下沉必须使用缩小后的 heap_size,否则会破坏排序结果。

示例中的计数排序只展开数值,因此不用于保持业务记录的相对顺序。若要稳定排序带附属数据的记录,需要累计计数并从右向左写入输出数组。键范围极大而数据稀疏时,计数数组可能耗尽内存,此时应改用比较排序或字典计数。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

堆排序与非比较排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通