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

Упражнения по сортировке Java [19 упражнений с решением]

[ Внизу страницы доступен редактор для написания и выполнения сценариев. ]

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

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

3. Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма сортировки Radix. Перейти к редактору
Согласно Википедии «В компьютерной науке радикальная сортировка представляет собой не сравнительный алгоритм целочисленной сортировки, который сортирует данные по целочисленным ключам путем группировки ключей по отдельным цифрам, которые имеют одинаковые значимые позиции и значения».
Нажмите меня, чтобы увидеть решение

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

5. Напишите Java-программу для сортировки массива заданных целых чисел с использованием алгоритма сортировки кучи. Перейти к редактору

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

6. Напишите программу на Java для сортировки массива заданных целых чисел с использованием алгоритма выбора сортировки. Перейти к редактору

Согласно Википедии «В компьютерной науке сортировка выбора является алгоритмом сортировки, в частности сортировкой по месту. Она имеет временную сложность O (n2), что делает ее неэффективной в больших списках и в целом работает хуже, чем аналогичная сортировка вставкой».
Нажмите меня, чтобы увидеть решение

7. Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки вставками. Перейти к редактору

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

8. Напишите Java-программу для сортировки массива натуральных чисел с использованием алгоритма сортировки бисера. Перейти к редактору
Согласно Википедии, «сортировка по бисеру, также называемая гравитационной сортировкой, является естественным алгоритмом сортировки, разработанным Джошуа Дж. Аруланандхамом, Кристианом С. Калуде и Майклом Дж. Диннином в 2002 году и опубликованным в Бюллетене Европейской ассоциации теоретических компьютерных наук». Как цифровые, так и аналоговые аппаратные реализации сортировки по бусинкам могут достигать времени сортировки O (n), однако реализация этого алгоритма, как правило, значительно медленнее в программном обеспечении и может использоваться только для сортировки списков положительных целых чисел. Казалось бы, даже в лучшем случае алгоритм требует O (n2) пробела ».
Нажмите меня, чтобы увидеть решение

9. Напишите программу на Java для сортировки массива натуральных чисел, используя алгоритм сортировки BogoSort. Перейти к редактору

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

10. Напишите Java-программу для сортировки массива натуральных чисел с использованием алгоритма сортировки Коктейля. Перейти к редактору

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

11. Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма CombSort. Перейти к редактору

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

12. Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма CountingSort. Перейти к редактору

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

13. Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки Gnome. Перейти к редактору

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

14. Напишите программу на Java для сортировки массива заданных целых чисел, используя алгоритм сортировки по Блину. Перейти к редактору

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

15. Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки перестановок. Перейти к редактору

Реализуйте сортировку перестановок, которая будет продолжаться путем генерации возможных перестановок входного массива / списка до обнаружения отсортированной.
Нажмите меня, чтобы увидеть решение

16. Напишите программу на Java для сортировки массива заданных целых чисел Алгоритм сортировки оболочки. Перейти к редактору

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

17. Напишите программу на Java для сортировки массива заданных неотрицательных целых чисел с помощью алгоритма сортировки сна. Перейти к редактору

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

18. Напишите Java-программу для сортировки массива заданных неотрицательных целых чисел с использованием алгоритма сортировки Stooge. Перейти к редактору

Сортировка по Стогу - это алгоритм рекурсивной сортировки с временной сложностью O ( n log 3 / log 1.5) = O ( n 2.7095 ...). Время выполнения алгоритма, таким образом, медленнее по сравнению с эффективными алгоритмами сортировки, такими как сортировка слиянием, и даже медленнее, чем сортировка Bubble.
Нажмите меня, чтобы увидеть решение

19. Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки по группам. Перейти к редактору

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

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

Еще не все !

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