代码拉取完成,页面将自动刷新
package sort
import (
"github.com/TheAlgorithms/Go/constraints"
)
// Cycle sort is an in-place, unstable sorting algorithm that is particularly useful
// when sorting arrays containing elements with a small range of values. It is theoretically
// optimal in terms of the total number of writes to the original array.
func Cycle[T constraints.Number](arr []T) []T {
counter, cycle, len := 0, 0, len(arr)
// Early return if the array too small
if len <= 1 {
return arr
}
for cycle = 0; cycle < len-1; cycle++ {
elem := arr[cycle]
// Find total smaller elements to right
pos := cycle
for counter = cycle + 1; counter < len; counter++ {
if arr[counter] < elem {
pos++
}
}
// In case this element is already in correct position, let's skip processing
if pos == cycle {
continue
}
// In case we have same elements, we want to skip to the end of that list as well, ignoring order
// This makes the algorithm unstable for composite elements
for elem == arr[pos] {
pos++
}
// Now let us put the item to it's right position
arr[pos], elem = elem, arr[pos]
//We need to rotate the array till we have reached the start of the cycle again
for pos != cycle {
pos = cycle
// Find smaller elements to right again
for counter = cycle + 1; counter < len; counter++ {
if arr[counter] < elem {
pos++
}
}
for elem == arr[pos] {
pos++
}
//We can do this unconditionally, but the check helps prevent redundant writes to the array
if elem != arr[pos] {
arr[pos], elem = elem, arr[pos]
}
}
}
return arr
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。