仅使用预计算排序获取已排序元素

Question

我在找一个算法。

比如说，有这样一个无序的列表：

main_list = np.array([100,200,400,1000,800,900,700,600,500,300])

还有一个查询列表元素 q = np.array([2,5,7,9])，这些元素对应于列表 np.array([400, 900, 600, 300])，我们需要直接从主列表中获取排序后的元素和它们的排序位置。

np.array([300, 400, 600, 900])
np.array([9,2,7,5])

主要的条件是：只使用已经计算好的排序数组，这样每次获取新查询时就不用再排序了。

编辑：在numpy中的解决方案（感谢 @cary-swoveland！）

首先，预先计算好排序的参数。这是一个离线步骤：

argsort = np.argsort(main_list)
argsort_argsort = np.argsort(argsort)

然后在查询时：

q = np.array([2,5,7,9])

new_array = np.full(main_list.shape[0], -1)
new_array[argsort_argsort[q]] = q

sorted_q = new_array[new_array != -1]
sorted_values = main_list[sorted_q]

print(sorted_q)
print(sorted_values)

结果：

[9 2 7 5]
[300 400 600 900]

Answer 1

创建一个数组，里面包含大小和位置，格式像这样：

[[400,2],[900,5],[600,7],[300,9]]

然后对这个数组进行排序，并把位置写入结果数组中。

Answer 2

这里有一个用Ruby写的解决方案，我觉得可以很容易地转换成其他编程语言。

我们有以下内容。

arr = [100, 200, 400, 1000, 800, 900, 700, 600, 500, 300]

第一步：生成一个包含排序后索引的数组

a = arr.each_index.sort_by { |i| arr[i] }
  #=> [0, 1, 9, 2, 8, 7, 6, 4, 5, 3]

这意味着

arr[a[i]] = arr.sort[i] 

比如说，如果 i = 2，

arr[a[2]] #=> arr[9] => 300
arr.sort[2] = 300

第二步：创建一个偏移量的排序数组

b = (0..arr.size-1).sort_by { |i| a[i] }
  #=> [0, 1, 3, 9, 7, 8, 6, 5, 4, 2]

b[2] #=> 3 的意思是 arr[2] = arr.sort[3]。

第三步：为每个给定的索引数组构建所需的数组

这个操作的时间复杂度是 O(n)，其中 n 是数组的大小。

假设

indices = [2,5,7,9]

所以

arr.values_at(*indices)
  #=> [400, 900, 600, 300]

首先创建一个包含 arr.size 个元素的数组，所有元素都初始化为 nil。

然后在正确的位置用 indices 的元素替换 c 的元素。

c = Array.new(arr.size)
  #=> [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil]

最后，移除 nil 元素。

indices.each { |idx| c[b[idx]] = idx }

c #=> [nil, nil, 9, 2, nil, 7, nil, nil, 5, nil]

并且

c.compact
  #=> [9, 2, 7, 5]

而且

arr.values_at(*c)
  #=> [300, 400, 600, 900]

---

同样地，如果

indices = [5, 3, 1, 7, 2]

那么

arr.values_at(*indices)
  #=> [900, 1000, 200, 600, 400]
c = Array.new(arr.size)
  #=> [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil]
indices.each { |idx| c[b[idx]] = idx }
c #=> [nil,   1, nil,   2, nil,   7, nil, nil,   5,   3]
d = c.compact
  #=> [1, 2, 7, 5, 3]
arr.values_at(*d)
  #=> [200, 400, 600, 900, 1000]