algorithm
Цикл сортировки
Поиск…
Цикл сортировки Основная информация
Cycle Sort - алгоритм сортировки, который использует сортировку сравнения, которая теоретически оптимальна с точки зрения общего количества записей в исходном массиве, в отличие от любого другого алгоритма сортировки на месте. Сортировка циклов - это неустойчивый алгоритм сортировки. Он основан на идее перестановки, в которой перестановки учитываются в циклах, которые индивидуально вращают и возвращают отсортированный результат.
Пример сортировки цикла:
Вспомогательное пространство: O(1)
Сложность времени: O(n^2)
Реализация псевдокода
(input)
output = 0
for cycleStart from 0 to length(array) - 2
item = array[cycleStart]
pos = cycleStart
for i from cycleStart + 1 to length(array) - 1
if array[i] < item:
pos += 1
if pos == cycleStart:
continue
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
while pos != cycleStart:
pos = cycleStart
for i from cycleStart + 1 to length(array) - 1
if array[i] < item:
pos += 1
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return outout
Реализация C #
public class CycleSort
{
public static void SortCycle(int[] input)
{
for (var i = 0; i < input.Length; i++)
{
var item = input[i];
var position = i;
do
{
var k = input.Where((t, j) => position != j && t < item).Count();
if (position == k) continue;
while (position != k && item == input[k])
{
k++;
}
var temp = input[k];
input[k] = item;
item = temp;
position = k;
} while (position != i);
}
}
public static int[] Main(int[] input)
{
SortCycle(input);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow