Алгоритм поиска и сортировки PHP - упражнения, практика, решение

Алгоритм поиска и сортировки PHP [17 упражнений с решением]

1. Напишите программу PHP для сортировки списка элементов с помощью быстрой сортировки. Перейти к редактору
Быстрая сортировка - это сортировка сравнения, это означает, что она может сортировать элементы любого типа, для которых определено отношение «меньше чем» (формально, общий порядок).
Нажмите меня, чтобы увидеть решение

2. Напишите программу PHP для сортировки списка элементов, используя сортировку кучи. Перейти к редактору
В информатике, heapsort (изобретенный JWJ Williams в 1964 году) является алгоритмом сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит свои входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, выделяя самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не линейного поиска времени, чтобы найти максимум. Хотя на некоторых машинах он работает несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществом более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort - это алгоритм на месте, но он не является стабильным.
Запуск алгоритма heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой кратко показана древовидная структура кучи для иллюстрации.
Нажмите меня, чтобы увидеть решение

3. Напишите программу PHP для сортировки списка элементов с использованием сортировки вставками. Перейти к редактору
Вставка сортировки - это простой алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен в больших списках, чем более продвинутые алгоритмы, такие как быстрая сортировка, heapsort или сортировка слиянием.
Нажмите меня, чтобы увидеть решение

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

5. Напишите PHP-программу для сортировки списка элементов с помощью Shell sort. Перейти к редактору
Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки пар элементы находятся далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».
Нажмите меня, чтобы увидеть решение

6. Напишите программу PHP для сортировки списка элементов, используя Bubble sort. Перейти к редактору
Согласно Википедии «Пузырьковая сортировка, иногда называемая тонкой сортировкой, представляет собой простой алгоритм сортировки, который последовательно проходит по списку для сортировки, сравнивает каждую пару смежных элементов и меняет их местами, если они находятся в неправильном порядке. Список повторяется до тех пор, пока не требуется перестановка, что указывает на сортировку списка. Алгоритм, который является сортировкой сравнения, назван так, как меньшие элементы «всплывают» в верхнюю часть списка. Хотя алгоритм прост, он является слишком медленным и непрактичным для большинства проблем, даже если сравнивать с сортировкой вставкой. Это может быть практичным, если входные данные обычно находятся в порядке сортировки, но иногда могут иметь некоторые неупорядоченные элементы, находящиеся почти на месте ».
Нажмите меня, чтобы увидеть решение

7. Напишите программу PHP для сортировки списка элементов, используя сортировку Коктейль. Перейти к редактору
Коктейльный шейкер (также известный как двунаправленная пузырьковая сортировка, коктейльная сортировка, шейкерная сортировка, пульсация, случайная сортировка или челночная сортировка) - это разновидность пузырьковой сортировки, которая является одновременно алгоритмом стабильной сортировки и сравнительной сортировкой. Алгоритм отличается от пузырьковой сортировки тем, что он сортирует в обоих направлениях при каждом проходе по списку. Этот алгоритм сортировки лишь немного сложнее в реализации, чем пузырьковая сортировка, и он решает проблему черепах в пузырьковых видах. Он обеспечивает лишь незначительные улучшения производительности и не улучшает асимптотическую производительность; Подобно пузырьковому типу, он не представляет практического интереса, хотя и находит некоторое применение в образовании.
Нажмите меня, чтобы увидеть решение

8. Напишите программу PHP для сортировки списка элементов с использованием Comb sort. Перейти к редактору
Расческа - это разновидность пузырчатой сортировки. Подобно сортировке «Шелл», сортировка «Гребень» увеличивает разрыв, используемый в сравнениях и обменах. Некоторые реализации используют сортировку вставкой, когда зазор меньше определенной величины. Основная идея состоит в том, чтобы исключить черепашек или небольшие значения в конце списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка, не представляют проблемы в пузырьковой сортировке.
В пузырьковой сортировке, когда сравниваются любые два элемента, они всегда имеют разрыв 1. Основная идея гребенчатой сортировки состоит в том, что разрыв может быть намного больше 1.
Нажмите меня, чтобы увидеть решение

9. Напишите программу PHP для сортировки списка элементов с использованием сортировки Gnome. Перейти к редактору
Сортировка гномов - это алгоритм сортировки, первоначально предложенный доктором Хамидом Сарбази-Азадом (профессором вычислительной техники в Шарифском технологическом университете) в 2000 году и названный «глупой сортировкой» (не путать с богосортом), а затем описанный Диком. Грун и назвал "гномом рода".
Алгоритм всегда находит первое место, где два соседних элемента находятся в неправильном порядке, и меняет их местами. Он использует тот факт, что выполнение обмена может привести к появлению новой неупорядоченной соседней пары только рядом с двумя замененными элементами.
Нажмите меня, чтобы увидеть решение

10. Напишите программу PHP для сортировки списка элементов, используя сортировку Bucket. Перейти к редактору
Нажмите меня, чтобы увидеть решение

11. Напишите PHP-программу для сортировки списка элементов с использованием сортировки Counting. Перейти к редактору
Согласно Википедии "В компьютерных науках сортировка подсчета - это алгоритм сортировки коллекции объектов по ключам, которые являются маленькими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количества объектов, у которых есть каждый отдельный ключ значение и использование арифметики по этим подсчетам для определения позиций каждого значения ключа в выходной последовательности. Время его выполнения линейно по количеству элементов и разности между максимальным и минимальным значениями ключа, поэтому оно подходит только для непосредственного использования в ситуациях, когда изменение в ключах не намного больше, чем количество элементов. Однако оно часто используется в качестве подпрограммы в другом алгоритме сортировки, основанном на сортировке, который может обрабатывать большие ключи более эффективно ».
Алгоритм зацикливается на элементах, вычисляя гистограмму того, сколько раз каждый ключ встречается в коллекции входных данных. Затем он выполняет вычисление суммы префикса (второй цикл по диапазону возможных ключей), чтобы определить для каждого ключа начальную позицию в выходном массиве элементов, имеющих этот ключ. Наконец, он снова зацикливается на элементах, перемещая каждый элемент в его отсортированную позицию в выходном массиве.
Нажмите меня, чтобы увидеть решение

12. Напишите программу PHP для сортировки списка элементов, используя сортировку Radix. Перейти к редактору
Нажмите меня, чтобы увидеть решение

13. Напишите программу PHP для сортировки списка элементов с использованием сортировки по бисеру. Перейти к редактору
Нажмите меня, чтобы увидеть решение

14. Напишите программу PHP для сортировки списка элементов, используя сортировку Bogo. Перейти к редактору
В информатике bogosort - это особенно неэффективный алгоритм сортировки, основанный на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своего ввода, пока не найдет отсортированный. Это не полезно для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его другим более реалистичным алгоритмам.
Нажмите меня, чтобы увидеть решение

15. Напишите программу PHP для сортировки списка элементов с использованием сортировки Strand. Перейти к редактору
Это способ сортировки чисел путем извлечения более коротких последовательностей уже отсортированных чисел из несортированного списка.
Нажмите меня, чтобы увидеть решение

16. Напишите программу PHP для сортировки списка элементов, используя сортировку Patience. Перейти к редактору
Сортировка терпения - это алгоритм сортировки, вдохновленный и названный в честь терпения карточной игры. Вариант алгоритма эффективно вычисляет длину самой длинной увеличивающейся подпоследовательности в данном массиве.
Название алгоритма происходит от упрощенного варианта карточной игры терпения. Эта игра начинается с перемешанной колоды карт. Эти карты раздаются одна за другой в последовательность стопок на столе в соответствии со следующими правилами.

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

Эта карточная игра превращается в алгоритм двухфазной сортировки следующим образом. Учитывая массив из n элементов из некоторого полностью упорядоченного домена, рассмотрите этот массив как набор карт и смоделируйте игру сортировки терпения. Когда игра закончится, восстановите отсортированную последовательность, неоднократно отбирая минимально видимую карту; Другими словами, выполните p-way слияние куч p, каждая из которых отсортирована внутри.

Нажмите меня, чтобы увидеть решение

17. Напишите программу PHP для сортировки списка элементов, используя сортировку слиянием. Перейти к редактору
Согласно Википедии «Сортировка слиянием (также обычно пишется слиянием) является алгоритмом сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированном выводе. "
Нажмите меня, чтобы увидеть решение

Еще не все !

Редактор кода PHP:

Еще не все !

Не отправляйте решение вышеупомянутых упражнений здесь, если вы хотите внести вклад, перейдите на соответствующую страницу упражнения.