Сортировка списка без использования методов Collection

Question

Как отсортировать список без использования методов Collection?

Answer 1

Дорожная карта

• Википедия / Алгоритм сортировки
  • Простые квадратичные алгоритмы
    • Bubble sort - для новичков
    • Выбор сортировки - очень интуитивно понятный
    • Сортировка вставок - также интуитивно понятна
  • Необходимая сортировка на основе сравнения
    • Сортировка слиянием - немного более продвинутая
    • Быстрая сортировка - пока пропустите, но посмотрите позже
  • Существенная несопоставимая сортировка
    • Подсчет сортировки - важно понять

Ваш первый алгоритм сортировки

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

1. Генерация 1000 случайных чисел в диапазоне от 0,9 (используйте java.util.Random для заполнения int[])
2. Сортируйте их, используя сортировку подсчета.

Как только вы это сделаете, вы поймете, насколько простой может быть сортировка, когда вы можете воспользоваться определенными свойствами чисел (в данном случае, фактом, что они находятся между 0..9).

Ваш второй алгоритм сортировки

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

• Учитывая некоторый выбор, мы ищем лучшее и выбираем его первым.
• Теперь лучшее вышло, поэтому мы ищем второе лучшее из остальных.
• Тогда мы ищем третий лучший ... и т.д.

Остальная часть пути

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

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

Выполняйте обычные рекурсивные упражнения, факториал, Фибоначчи и т. Д. Попросите указатели из stackoverflow, если вам нужно руководство. Возможно, уже есть вопросы с хорошими ответами об обучении рекурсии.

Боковой проезд

Возможно, вы захотите внедрить часть слияния сортировки слиянием, даже до того, как полностью поймете рекурсию. Это очень познавательное упражнение:

• Учитывая отсортированный массив чисел A и отсортированный массив чисел B, объедините два в один отсортированный массив
  • Воспользуйтесь тем, что A и B уже отсортированы

Answer 2

Поскольку это, скорее всего, домашнее задание, я дам вам совет, а не исходный код.

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

Если у вас есть только небольшое количество элементов и вы хотите простой алгоритм, вы можете посмотреть сортировка вставок . Страница Википедии содержит псевдокод. Этот алгоритм имеет производительность O (n ^ 2).

Если ваши списки довольно длинные и вы хотите повысить производительность за счет немного более сложного алгоритма, вы можете попробовать сортировка слиянием . Этот алгоритм имеет производительность O (n log (n)) как в среднем, так и в худшем случае и является популярным выбором в языковых библиотеках.