实现APL向量monadic grade up的高性能稳定算法有哪些？

通用O(n log n) 实现思路 #

适配通用排序算法的方案非常简单，不需要修改原输入向量V，核心是对下标序列做排序：

• 步骤1：初始化长度为n的结果数组R，填充为R[i] = i（i从0到n-1），即初始为原始下标序列
• 步骤2：对R数组执行排序，比较规则定义为：下标a排在下标b前面的条件是V[a] < V[b]，如果V[a] == V[b]则要求a < b
• 步骤3：排序完成后的R就是符合要求的grade up返回值

该方案的优势是不依赖排序算法本身的稳定性：因为我们把比较键从单一的V取值扩展为了二元组(V[x], x)，所有比较键全局唯一，哪怕用非稳定排序算法（比如快速排序、堆排序），最终结果也天然满足grade up的稳定性要求，等值元素的下标一定会按原始顺序排列。

伪代码示例 #

function gradeUp(V):
    n = length(V)
    // 初始化下标数组
    R = array from 0 to n-1
    // 按自定义规则排序
    sort(R, comparator(a, b):
        if V[a] != V[b]:
            return V[a] < V[b]
        return a < b
    )
    return R

效果验证示例 #

假设输入V = [3, 1, 2, 1]，按上述步骤执行：

1. 初始R = [0, 1, 2, 3]
2. 排序后R = [1, 3, 2, 0]
3. 验证：V[1]=1、V[3]=1、V[2]=2、V[0]=3，等值的下标1<3按顺序保留，完全符合grade up的要求。

常量额外空间实现方案 #

如果要求仅用O(1)额外空间（不计入输入向量V和输出数组R的预分配空间），可以做如下适配：

• 选择就地排序算法实现上述排序逻辑，优先选择堆排序：堆排序为原生就地排序，仅需固定数量的临时变量，额外空间开销为O(1)，时间复杂度稳定为O(n log n)
• 不需要修改原输入向量V，所有比较操作仅读取V的取值，所有交换操作都在预分配的R数组上执行

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