循环排序
P
"""
Code contributed by Honey Sharma
Source: https://en.wikipedia.org/wiki/Cycle_sort
"""
def cycle_sort(array: list) -> list:
"""
>>> cycle_sort([4, 3, 2, 1])
[1, 2, 3, 4]
>>> cycle_sort([-4, 20, 0, -50, 100, -1])
[-50, -4, -1, 0, 20, 100]
>>> cycle_sort([-.1, -.2, 1.3, -.8])
[-0.8, -0.2, -0.1, 1.3]
>>> cycle_sort([])
[]
"""
array_len = len(array)
for cycle_start in range(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]
关于此算法
问题陈述
给定一个包含 n 个元素的未排序数组，编写一个函数对数组进行排序。
方法
- 如果元素已在正确的位置，则不执行任何操作。
- 否则，通过计算小于当前元素的元素总数来找到 a 的正确位置。
- 将当前元素插入其正确的位置。
- 将替换的元素设置为新的当前元素并找到其正确位置。
- 继续此过程，直到数组排序完成。
时间复杂度
O(n^2) 最坏情况性能
O(n^2) 最佳情况性能
O(n^2) 平均性能
空间复杂度
O(n) 最坏情况
算法应用
- 循环排序算法适用于内存写入或元素交换操作代价高昂的情况。
示例
数组排序的一个循环 | b | d | e | a | c |
1. Select element for which the cycle is run, i.e. "b".
|b|d|e|a|c|
b - current element
2. Find correct location for current element and update current element.
|b|b|e|a|c|
d - current element
3. One more time, find correct location for current element and update current element.
|b|b|e|d|c|
a - current element
4. Current element is inserted into position of initial element "b" which ends the cycle.
|a|b|e|d|c|
a - current element
5. New cycle should be started for next element.
