0

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

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]]

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

提前致谢。

4

3 回答 3

1

实际上，您的算法不是排序算法。这是一种计算 上排列的逆的算法0..n。换句话说，它将告诉您如何重新排列 A 以使所有数字都到位。

为什么不是排序算法？ 如果 A 包含 0..n 范围内的所有数字，则排序后的数组将始终为 B = [0, 1, 2, ..., n]。另一方面，如果 A 有重复项，则此算法将不起作用。我认为您要做的是对 sort 进行计数。该算法适用于 A 是一个大小为数组k且包含范围内的数字的情况0..n。该算法有一个大小为 B 的数组n+1，它计算每个数字在 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
于 2013-04-04T10:45:38.953 回答
0

I think you've got a pigeon hole sort there

于 2013-04-04T10:47:58.493 回答
0

在这里阅读桶排序后，它看起来像桶大小为 1 的桶排序。

在桶排序中，将元素放入桶中后，对每个桶进行排序。

但是，在您的情况下，由于存储桶大小为 1，因此不需要此步骤。也不需要合并存储桶，因为存储桶大小为 1 并且已经合并到数组中。

于 2013-04-04T10:36:16.183 回答