algorithm - 这个排序算法叫什么？

Question

我在考虑一种非比较排序算法，我想我自己找到了一个。

Input: A[0...n] ranged from 0...n //ideally, I think it can be expanded to more general case later

Non-comparison-sort(A,n):
let B = [0...n] = [0]
for i in A:
    B[A[i]]=i

经过这个算法，数组B中的每个元素都会有一个数组A的引用，如果我们想访问值为m的A[k]，我们可以使用A[B[m]]

我确定我不是第一个想到这个想法的人，所以我的问题是这个算法叫什么？

提前致谢。

Answer 1

实际上，您的算法不是排序算法。这是calculate the inverse of a permutation的算法在 0..n 上。换句话说，它将告诉您如何重新排列 A 以使所有数字都到位。

为什么不是排序算法？ 如果 A 包含 0..n 范围内的所有数字，则排序后的数组将始终为 B = [0, 1, 2, ..., n]。另一方面，如果 A 有重复项，则此算法将不起作用。 我想你想要做的是 counting sort .该算法适用于 A 是大小为 k 的数组，并且包含 0..n 范围内的数字的情况。该算法有一个大小为 n+1 的数组 B，它计算每个数字在 A 上迭代一次时出现的次数。

计数排序的示例(在您的伪代码语法中):

Counting-sort(A, n):
  let B = [0...n] = [0]
  for x in A:
    B[x] = B[x] + 1
  let C = [] // an empty list
  for i in 0...n:
    for j in 0...B[i]: // add each number 0..n the number of times it appeared in A
      C.append(i)
  return C