基于StaticArray的计数排序实现遇索引越界错误求助

算法课程作业任务：需实现一个时间复杂度为O(n+k)的计数排序函数，接收StaticArray输入，返回原数组非升序排列的新StaticArray，原数组不可修改。禁止使用内置函数及遍历数组的for循环，仅允许遍历数值范围的for循环。已知输入元素为[-10^9,109]内的整数，最大最小值差小于1000，需支持至少500万元素高效排序。

本人编写的代码运行时抛出StaticArray索引越界异常，以下是代码、StaticArray类定义及报错堆栈信息，请求排查错误并给出修复方案：

本人代码 #

low = min_max(arr)[0]
high = min_max(arr)[1]
arr_size = StaticArray.length(arr)
result = StaticArray(arr_size)
count_array = StaticArray(high - low + 1)
# initialize result and count_array to have 0 at all indices
for num in range(0, count_array.length()):
    count_array[num] = 0
for num in range(0, result.length()):
    result[num] = 0
# count the occurence of each item 
num = 0
while num < arr_size:
    pos = arr[num]
    count_array[pos - low] += 1  # offset indexing
    num += 1
# back sum
for j in range(1, count_array.length()):
    count_array[j] += count_array[j - 1]
# place value in result array
num = arr_size - 1
while num >= 0:
    result[count_array[arr[num]] - 1] = arr[num]
    count_array[arr[num]] -= 1
    num -= 1
return result

StaticArray类定义 #

class StaticArray:
    """
    静态数组数据结构的实现。
    已实现方法：get(), set(), length()

    禁止修改此类。

    即使你修改了自己的StaticArray文件并随作业上传到Gradescope，也不会生效。Gradescope使用自己的StaticArray文件（与此文件完全一致），额外提交的StaticArray文件会被忽略。
    """

    def __init__(self, size: int = 10) -> None:
        """
        创建指定大小的数组。
        所有元素初始化为None。
        如果请求的大小不是正数，抛出StaticArray异常。
        """
        if size < 1:
            raise StaticArrayException('数组大小必须为正整数')

        # 下划线表示这是私有变量，不应直接访问。
        # 使用length()方法获取StaticArray的大小。
        self._size = size

        # 注意，这里用的是内置列表，因为Python没有固定大小的数组类型。
        # 不要在你的作业中这样初始化变量！
        self._data = [None] * size

    def __iter__(self) -> None:
        """
        禁用StaticArray类的迭代器功能。
        这意味着如下所示的循环和聚合函数将无法工作：

        arr = StaticArray()
        for value in arr:     # 无法工作
        min(arr)              # 无法工作
        max(arr)              # 无法工作
        sort(arr)             # 无法工作
        """
        return None

    def __str__(self) -> str:
        """重写字符串方法以提供更易读的输出。"""
        return f"STAT_ARR 大小: {self._size} {self._data}"

    def get(self, index: int):
        """
        返回指定索引位置的值。
        无效索引会抛出StaticArrayException。
        """
        if index < 0 or index >= self.length():
            raise StaticArrayException('索引越界')
        return self._data[index]

    def set(self, index: int, value) -> None:
        """
        将值存储到数组的指定索引位置。
        无效索引会抛出StaticArrayException。
        """
        if index < 0 or index >= self.length():
            raise StaticArrayException('索引越界')
        self._data[index] = value

    def length(self) -> int:
        """返回数组的长度（元素个数）。"""
        return self._size

报错信息 #

Traceback (most recent call last):
  File "/Users/deleted for privacy/Desktop/CS261/assignment1/assignment1.py", line 414, in <module>
    result = count_sort(arr)
             ^^^^^^^^^^^^^^^
  File "/Users/deleted for privacy/Desktop/CS261/assignment1/assignment1.py", line 247, in count_sort
    result[count_array[arr[num]] - 1] = arr[num]
           ~~~~~~~~~~~^^^^^^^^^^
  File "/Users/deleted for privacy/Desktop/CS261/assignment1/static_array.py", line 87, in __getitem__
    return self.get(index)
           ^^^^^^^^^^^^^^^
  File "/Users/deleted for pr/Desktop/CS261/assignment1/static_array.py", line 73, in get
    raise StaticArrayException('索引越界')
static_array.StaticArrayException: 索引越界

核心错误原因 #

1. 索引偏移缺失：在放置元素到结果数组的阶段，直接用arr[num]作为count_array的索引，没有减去low做偏移。count_array的大小是high - low + 1，索引范围仅为0到high-low，而arr[num]的取值是low到high，直接访问必然导致索引越界。
2. 排序方向不符合要求：题目要求非升序排列，但当前代码是按升序逻辑实现的，计数数组的累加方向和元素放置逻辑都需要调整。

修复后的代码 #

def count_sort(arr):
    low = min_max(arr)[0]
    high = min_max(arr)[1]
    arr_size = StaticArray.length(arr)
    result = StaticArray(arr_size)
    count_array = StaticArray(high - low + 1)
    
    # 初始化计数数组为0
    for num in range(count_array.length()):
        count_array[num] = 0
    
    # 统计每个元素出现次数
    num = 0
    while num < arr_size:
        current_val = arr[num]
        count_array[current_val - low] += 1
        num += 1
    
    # 反向累加计数数组（适配非升序排序）
    for j in range(count_array.length() - 2, -1, -1):
        count_array[j] += count_array[j + 1]
    
    # 从后往前遍历原数组，放置元素到结果数组
    num = arr_size - 1
    while num >= 0:
        current_val = arr[num]
        count_idx = current_val - low  # 计算正确的计数数组索引
        result_pos = count_array[count_idx] - 1
        result[result_pos] = current_val
        count_array[count_idx] -= 1
        num -= 1
    
    return result

关键修复点说明 #

• 补全索引偏移：所有访问count_array的操作都使用current_val - low计算索引，确保在数组有效范围内。
• 调整累加方向：将计数数组的累加逻辑从正向改为反向（从倒数第二个元素遍历到第一个），使计数数组存储当前元素及更大元素的总个数，满足非升序的位置计算需求。
• 优化变量复用：提取current_val和count_idx变量，避免重复计算，提升代码可读性和执行效率。

内容的提问来源于stack exchange，提问作者gem's_dad