Python:實現cycle sort循環排序算法
def cycle_sort(array: list) -> list:
array_len = len(array)
for cycle_start in range(0, array_len - 1):
item = array[cycle_start]
pos = cycle_start
for i in range(cycle_start + 1, array_len):
if array[i] < item:
pos += 1
if pos == cycle_start:
continue
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
while pos != cycle_start:
pos = cycle_start
for i in range(cycle_start + 1, array_len):
if array[i] < item:
pos += 1
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
return array
if __name__ == "__main__":
assert cycle_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
assert cycle_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]
