Вас може зацікавити яким чином метод sort () сортує список. Зазвичай, якщо подивитися на алгоритм сортування в книзі по алгоритмам, він представляється для масивів з використанням довільного доступу до елементів. Однак довільний доступ до елементів списку неефективний.
Ви можете ефективно сортувати списки, використовую форму сортування злиттям. Однак реалізація на мові Java не робить цього. Вона просто скидає всі елементи в масив, сортує цей масив, застосовуючи інший варіант сортування злиттям, і потім копіює відсортовану послідовність назад в список.
Алгоритм сортування злиттям, який використовується в бібліотеці колекцій, трохи повільніше швидкого сортування (quick sort) - традиційного вибору для алгоритмів сортування загального призначення. Однак він має одну важливу перевагу: він стабільний, тобто не міняє місцями еквівалентні елементи.
Навіщо турбуватися про порядок еквівалентних елементів? Розглянемо поширений сценарій. Припустимо, що у вас є список співробітників, який ви вже відсортували по іменах. Тепер ви сортуєте із зарплати. Що трапиться з співробітниками з однаковою зарплатою? При стабільній сортування порядок по іменах зберігається. Іншими словами, в результаті отримаємо список, відсортований спочатку по зарплаті, потім по імені.
Оскільки колекціями не обов'язково реалізовувати всі «необов'язкові» методи, все методи, які беруть параметри-колекції, повинні вказувати, коли передавати колекцію алгоритму безпечно. Наприклад, очевидно, що ви не захочете передати список unmodifiableList алгоритму сортування. Якого роду списки ви можете передавати? Згідно з документацією, список повинен бути модифікується, але не повинен бути змінним в розмірі.
Терміни визначаються наступним чином:
- Список є модифікується, якщо він підтримує метод set ().
- Список є змінним у розмірі, якщо він підтримує методи add () і remove ().
Клас Collections має алгоритм shuffle. який виконує протилежну сортування завдання: випадковим чином змінює порядок елементів у списку.
Collections. shuffle (cards);
Якщо ви застосуєте список, який не реалізує інтерфейс RandomAccess. то метод shuffle скопіює всі елементи в масив, перетасує цей масив, після чого скопіює перетасовані елементи назад в список.
Програма яка приведена нижче заповнює масив-список 49 об'єктами Integer. що містять числа від 1 до 49. Потім вона випадково тасує їх в списку і вибирає перші 6 значень з перетасувати списку. І, нарешті, вона сортує обрані значення і друкує їх.
Ось власне програма яка демонструє алгоритми випадкового тасування і сортування: