如何用Counting Sort对带初始索引的数组进行排序

核心思路 #

你的主数组元素取值范围极小（0~6），计数排序的时间复杂度为O(n+k)（n是数组长度，k是取值范围），完全适配这个场景。要同步维护原索引的辅助数组，关键是用桶存储每个数值对应的原索引列表（而非仅统计次数），再按降序遍历数值，依次填充主数组和辅助数组。

具体实现步骤 #

以你的示例数组为例：

• 初始主数组：main_arr = [0, 3, 5, 1, 0, 2, 4]
• 初始索引数组：idx_arr = [0, 1, 2, 3, 4, 5, 6]

1. 确定取值范围：找到主数组的最大值max_val=5和最小值min_val=0，取值范围为0~5。
2. 创建索引桶：初始化一个长度为max_val - min_val + 1的列表，每个元素是一个空列表，用于存储对应数值的原索引。
3. 填充索引桶：从后往前遍历原数组，将当前元素的原索引加入对应数值的桶中——这样能保证相同数值的元素，原索引大的排在前面，完全匹配你给出的示例结果。
4. 生成排序后的数组：从最大值到最小值遍历数值，依次将数值填充到结果主数组，同时将对应桶中的索引依次填充到结果辅助数组。

代码示例（Python） #

def counting_sort_with_index(main_arr):
    n = len(main_arr)
    if n == 0:
        return [], []
    
    # 确定取值范围
    max_val = max(main_arr)
    min_val = min(main_arr)
    range_val = max_val - min_val + 1
    
    # 初始化索引桶
    buckets = [[] for _ in range(range_val)]
    
    # 从后往前遍历填充桶，保证相同数值的原索引大的在前
    for idx in reversed(range(n)):
        val = main_arr[idx]
        bucket_idx = val - min_val
        buckets[bucket_idx].append(idx)
    
    # 生成结果数组
    sorted_main = []
    sorted_idx = []
    # 降序遍历数值范围
    for val in reversed(range(min_val, max_val + 1)):
        bucket_idx = val - min_val
        # 取出桶内所有索引，依次加入结果
        for idx in buckets[bucket_idx]:
            sorted_main.append(val)
            sorted_idx.append(idx)
    
    return sorted_main, sorted_idx

# 测试示例
main_arr = [0, 3, 5, 1, 0, 2, 4]
sorted_main, sorted_idx = counting_sort_with_index(main_arr)
print("排序后主数组:", sorted_main)  # 输出: [5, 4, 3, 2, 1, 0, 0]
print("排序后辅助数组:", sorted_idx)  # 输出: [2, 6, 1, 5, 3, 4, 0]

关键细节说明 #

• 桶的作用：相比普通计数排序仅统计次数，用桶存储原索引能直接关联排序后元素的原始位置，满足辅助数组的需求。
• 遍历顺序调整：若需要相同数值的元素按原索引升序排列，只需将填充桶的遍历顺序改为从前往后即可。
• 排序方向切换：如果要实现主数组升序排序，只需将生成结果时的数值遍历顺序改为从min到max。

内容的提问来源于stack exchange，提问作者GH228