Блог

Я пытаюсь использовать рекурсивную функцию для сортировки массива в порядке возрастания. Загвоздка в том, что я не могу использовать циклы for , while или do / while. В Интернете есть множество ресурсов для сортировки по выбору, но мне трудно найти что-либо без циклов, а также с указанием указателя.

Краткий пошаговый обзор того, что я пытаюсь сделать.

1. Поместите маркер в первый элемент массива

2. Если маркер указывает на последний элемент массива, затем остановитесь. В противном случае продолжить

3. Найдите наименьший элемент справа от маркера

4. Если этот элемент меньше, чем элемент, на который указывает маркер, затем поменяйте местами

5. Переместите маркер к следующему элементу справа

6.Перейдите к шагу 2

По крайней мере, вы можете спроектировать его, используя циклы, и преобразовать циклы.

Любой цикл может быть преобразован в следующую форму:

 State state = init();
while (cond(amp;state))
   body(amp;state);
tail(amp;state);
 

И этот цикл может быть реализован тривиально с использованием рекурсии.

 void recursive(State *state) {
   if (!cond(state))
      return;

   body(state);
   recursive(state);
}

State = state = init();
recursive(amp;state);
tail(amp;state);
 

Тем не менее, гораздо проще решить эту проблему напрямую.

Сортировка выборки тривиальна для реализации с использованием рекурсии. В целом, вы повторно сортируете постоянно уменьшающуюся часть массива. После замены первого элемента на наименьший элемент вам необходимо отсортировать оставшуюся часть массива, что можно легко сделать с помощью рекурсивного вызова.

Это оставляет цикл для поиска наименьшего элемента массива. Опять же, это тривиально определить в терминах самого себя. Наименьший элемент списка — это наименьший из первого элемента и наименьший элемент остальной части списка.