我在浏览互联网时发现有一种叫做循环排序的算法可以使内存写入最小化。但我找不到该算法的任何资料。如何检测数组中是否存在循环?有人能给出这个算法的完整解释吗?
我在浏览互联网时发现有一种叫做循环排序的算法可以使内存写入最小化。但我找不到该算法的任何资料。如何检测数组中是否存在循环?有人能给出这个算法的完整解释吗?
4 3 0 1 2
让我们想象一下,我们有一个按照顺序排序的序列,如下所示:
0 1 2 3 4
0 1 2 3 4
4 3 0 1 2
如果有人需要,这里是一个Python实现
def cycleSort(vector):
writes = 0
# Loop through the vector to find cycles to rotate.
for cycleStart, item in enumerate(vector):
# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1
# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue
# Otherwise, put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart:
# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1
# Put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1
return writes
x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
w = cycleSort(x)
print w, x