什么是实现 APL 升级的高性能算法？
What is a performant algorithm for implementing APL grade up?
对于 APLers：我只关心向量上的单子级。
对于非 APL 用户：Grade up 是一个函数，它采用大小为 n 和 returns 的数值向量 V一个大小相等的整数向量 R。 V的最小元素的索引放在R[0]中，R中下一个最小元素的索引[1], ..., V在R[n[=38中的最大元素=]-1]。 V的值必须不变。
分级显然与排序有关：R提供索引到V以访问V 排序。升级必须是稳定的：也就是说，如果 V 的两个元素具有索引 i, j 其中 i < j相等，则i,j将依次出现在R中，并按此顺序排列。 O(n^2) 实现很简单，但我不知道如何适应标准稳定 O(n log n) 用于此目的的排序实现。只使用常量 space 的算法是可取的。
对于这个特定的任务，您可以使用任何就地排序算法：用从 0 到 n-1 的索引填充 R，然后对其进行排序。
对于排序，不是按值比较两个索引 i 和 j，而是比较 V[i ] 到 V[j]。如果它们相等，then 通过比较 i 和 j.
打破平局
由于没有两个索引会比较相等，即使像 Quicksort 这样不稳定的算法也会产生稳定的结果。许多语言都包含一个默认排序，它将比较函数作为输入。
对于 APLers：我只关心向量上的单子级。
对于非 APL 用户：Grade up 是一个函数，它采用大小为 n 和 returns 的数值向量 V一个大小相等的整数向量 R。 V的最小元素的索引放在R[0]中，R中下一个最小元素的索引[1], ..., V在R[n[=38中的最大元素=]-1]。 V的值必须不变。
分级显然与排序有关：R提供索引到V以访问V 排序。升级必须是稳定的：也就是说，如果 V 的两个元素具有索引 i, j 其中 i < j相等，则i,j将依次出现在R中，并按此顺序排列。 O(n^2) 实现很简单，但我不知道如何适应标准稳定 O(n log n) 用于此目的的排序实现。只使用常量 space 的算法是可取的。
对于这个特定的任务，您可以使用任何就地排序算法：用从 0 到 n-1 的索引填充 R，然后对其进行排序。
对于排序，不是按值比较两个索引 i 和 j，而是比较 V[i ] 到 V[j]。如果它们相等，then 通过比较 i 和 j.
打破平局由于没有两个索引会比较相等，即使像 Quicksort 这样不稳定的算法也会产生稳定的结果。许多语言都包含一个默认排序，它将比较函数作为输入。