這個排序算法叫做什麼？

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那裏