这个排序算法叫做什么？

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的引用，并说，如果我们想访问A [k]的它的值是米，我们可以用A [B [M]]

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

在此先感谢。

Answer 1

阅读桶排序here后，它看起来像桶排序，其中桶的大小为1

在桶排序，把元素桶后，每个桶是由排序。

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

Answer 2

其实，你的算法是而不是的一种排序算法。这是0..n上calculate the inverse of a permutation的算法。换句话说，它会告诉你如何重新排列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 

Answer 3

我认为你已经有pigeon hole sort那里