algorithm
Odd-Even Сортировать
Поиск…
Нечетная-четная сортировка
Сорт Odd-Even Sort или Brick - это простой алгоритм сортировки, который разработан для использования на параллельных процессорах с локальной связью. Он работает, сравнивая все нечетные / четные индексы пары смежных элементов в списке и, если пара находится в неправильном порядке, элементы переключаются. Следующий шаг повторяет это для четных / нечетных индексированных пар. Затем он чередуется между нечетными / четными и четными / нечетными шагами, пока список не будет отсортирован.
Псевдокод для Odd-Even Сортировать:
if n>2 then
1. apply odd-even merge(n/2) recursively to the even subsequence a0, a2, ..., an-2 and to the odd subsequence a1, a3, , ..., an-1
2. comparison [i : i+1] for all i element {1, 3, 5, 7, ..., n-3}
else
comparison [0 : 1]
В Википедии есть лучшая иллюстрация типа Odd-Even:
Пример Odd-Even Сортировать:
Реализация:
Я использовал язык C # для реализации Odd-Even Sort Algorithm.
public class OddEvenSort
{
private static void SortOddEven(int[] input, int n)
{
var sort = false;
while (!sort)
{
sort = true;
for (var i = 1; i < n - 1; i += 2)
{
if (input[i] <= input[i + 1]) continue;
var temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
sort = false;
}
for (var i = 0; i < n - 1; i += 2)
{
if (input[i] <= input[i + 1]) continue;
var temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
sort = false;
}
}
}
public static int[] Main(int[] input)
{
SortOddEven(input, input.Length);
return input;
}
}
Вспомогательное пространство: O(n)
Сложность времени: O(n)
Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow