pta插入排序还是堆排序

### PTA平台上插入排序与堆排序的实现

#### 插入排序的实现
对于给定的一组数列，在判断其为插入排序的情况下，程序会继续模拟一次完整的插入排序过程并输出结果。如果中间序列的一部分已经有序而另一部分保持原样无序，则可以断定这是插入排序的过程[^2]。

def insertion_sort_next_round(initial, current):
    n = len(current)
    
    # 找到第一个未排序的位置
    i = 0
    while i < n and initial[i] == current[i]:
        i += 1
    
    if i >= n or all(x <= y for x, y in zip(current[:i], current[1:i+1])):
        pos = i
        
        # 进行下一轮插入操作
        key = current[pos]
        j = pos - 1
        while j >= 0 and current[j] > key:
            current[j + 1] = current[j]
            j -= 1
        current[j + 1] = key
        
        return "Insertion Sort", current
    else:
        return None, []

#### 堆排序的实现
当确认是堆排序时，意味着当前数组是从最大堆调整而来。为了完成下一步的操作，需要找出堆顶元素应该交换至的具体位置，并据此更新整个数组的状态[^4]。

import heapq

def heapify(arr, index=0, size=None):
    if size is None:
        size = len(arr)

    largest = index
    left_child = 2 * index + 1
    right_child = 2 * index + 2

    if left_child < size and arr[left_child] > arr[largest]:
        largest = left_child

    if right_child < size and arr[right_child] > arr[largest]:
        largest = right_child

    if largest != index:
        arr[index], arr[largest] = arr[largest], arr[index]

        heapify(arr, largest, size)


def next_heap_sort_step(initial, current):
    sorted_part = list(reversed(sorted(current)))
    unsorted_part_start = sum(1 for a, b in zip(initial[::-1], sorted_part) if a == b)

    temp_arr = current.copy()
    last_element_index = len(temp_arr) - unsorted_part_start - 1
    temp_arr[last_element_index], temp_arr[0] = temp_arr[0], temp_arr[last_element_index]
    heapify(temp_arr, size=len(temp_arr)-unsorted_part_start-1)

    return "Heap Sort", temp_arr

---

### 性能对比分析

通常情况下，两种算法的时间复杂度分别为：

- **插入排序**：平均时间复杂度 O(n²)，但在接近已排序的数据集上表现较好，因为每次只需要移动少量元素即可维持顺序。

- **堆排序**：最坏情况下的时间复杂度稳定于 O(n log n)，适用于处理较大规模且随机分布的数据集合[^1]。

因此，在PTA平台上的具体应用场景中，选择哪种排序方法取决于待排序列表的特点以及预期达到的效果。对于几乎已经是有序的小型数据集来说，插入排序可能更高效；而对于大型或完全无序的数据集，则应优先考虑使用堆排序来获得更好的性能。