我想出了一個晦澀難懂的排序演算法，考慮到它如此簡單，它肯定是以前被發明和命名的，所以我想知道它叫什么。
它有一個非常罕見的限制：它僅適用于具有從0to n-1（或等效鍵）的輸入。這是一個非常強大的約束，使其在實踐中毫無用處，但也許可以構建一些有用的人為設定。該演算法基本上將特定位置的元素與其最終位置交換，直到陣列被排序。偽代碼：
def obscure_sort(array):
sorted_until = 1
while true
if key(array[0]) != 0:
# Swap the element at position 0 to its final position.
swap(array, 0, key(array[0]))
else:
# Find the next element that isn't in its final position.
while key(array[sorted_until]) == sorted_until:
sorted_until
# If we happen to reach the end, we're done.
if sorted_until == array.length:
return
# Swap the newfound first unsorted element to position 0
swap(array, 0, sorted_until)
該演算法實際上在O(n). 看到這一點并非微不足道，除非有人真正感興趣，否則我將省略分析。
有誰知道這個有名字嗎？
uj5u.com熱心網友回復：
這是受限回圈排序的輕微變體，可能最接近本文第 3 節中的演算法。
通常對鍵進行回圈排序A = [0, 1,...(A.length-1)]，您將遍歷陣列測驗索引0 to A.length-1作為“回圈開始”，尋找要旋轉的回圈。一次“旋轉”是通過始終持有一個臨時變數“temp”（最初是我們的回圈開始）來完成的，然后執行 aswap(temp, A[temp])直到我們回到回圈的開始（即，當 temp == A[temp] 時）。
相比之下，我們在這里在回圈的后面添加 0，并且 'A[0]' 代替了 'temp'。我們使用 operation swap(A[0], A[A[0]])，所以一般來說，移動的元素 x 需要經過 A[old] -> A[0] -> A[x] 而不是 A[temp] -> temp -> A[x] .
在上述論文中描述的線性時間演算法中，在開始回圈迭代時i，所有元素0, 1, ..., i-1都在原位并且不再移動。這個演算法是類似的，除了如果它是用相同的回圈風格撰寫的，0, 1, ..., i-1也在迭代開始時就位，i但元素 0 不是固定的，在迭代程序中不斷移動。
作為一個小例子：
Traditional Cycle Sort
Initially, A = [1, 3, 0, 2]
Step 1: A = [1, 3, 0, 2], temp = 1, with cycle_start = 0
Step 2: A = [1, 1, 0, 2], temp = 3
Step 3: A = [1, 1, 0, 3], temp = 2
Step 4: A = [2, 1, 2, 3], temp = 0
Step 5: A = [0, 1, 2, 3], temp = 2; stop since temp == A[temp]
Custom Cycle-like Sort
A = [1, 3, 0, 2]
Step 1: A = [1, 3, 0, 2]
Step 2: A = [3, 1, 0, 2]
Step 3: A = [2, 1, 0, 3]
Step 4: A = [0, 1, 2, 3]
請注意，這種新排序可以比正常回圈排序采取更多步驟，因為“在回圈后面添加 0”可以在每個回圈中添加額外的交換操作。但是，陣列交換的總數是線性的（最多是陣列長度的兩倍）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344381.html
上一篇：如何向陣列添加越來越多的內容