Меню

Сортування бульбашок на Java - алгоритми сортування Java та приклади коду

  • Головна
  • Інший
  • Сортування бульбашок на Java - алгоритми сортування Java та приклади коду

bubble sort java java sorting algorithms code examples

Спробуйте Наш Інструмент Для Усунення Проблем

Цей посібник пояснить сортування міхурів на Java, а також основні алгоритми сортування Java, реалізацію сортування міхурів та приклади коду:

Алгоритм сортування може бути визначений як алгоритм або процедура розміщення елементів колекції в певному порядку. Наприклад, якщо у вас є числова колекція, як ArrayList цілих чисел, то, можливо, ви захочете розташувати елементи ArrayList у порядку зростання або зменшення.

Так само, можливо, ви захочете впорядкувати рядки набору рядків в алфавітному або лексикографічному порядку. Ось тут і з’являються алгоритми сортування на Java.

реалізація програми хешування на c ++

Техніка сортування міхурів на Java

Що ви дізнаєтесь:

Основні алгоритми сортування в Java

Алгоритми сортування зазвичай оцінюються залежно від часової та просторової складності. Java підтримує різні алгоритми сортування, які використовуються для сортування або упорядкування колекцій або структур даних.

У таблиці нижче наведено основні алгоритми сортування, що підтримуються Java, а також їх найкращі / найгірші випадки.

Складність часу
Сортування RadixАлгоритм лінійного сортування.O (nk)O (nk)O (nk)
Алгоритм сортування Опис Кращий випадок Найгірший випадок Середній випадок
Сортування бульбашокПорівнює поточний елемент із сусідніми елементами неодноразово. В кінці кожної ітерації найважчий елемент потрапляє у відповідне місце.O (n)O (n ^ 2)O (n ^ 2)
Сортування вставкиВставляє кожен елемент колекції у відповідне місце.O (n)O (n ^ 2)O (n ^ 2)
Сортувати злиттяЦе слідує підходу 'розділи і завоюй'. Розділяє колекцію на простіші підколекції, сортує їх, а потім об’єднує всеO (nlogn)O (nlogn)O (nlogn)
Швидке сортуванняНайефективніша та оптимізована техніка сортування. Використовує розділити та завоювати для сортування колекції.O (nlogn)O (n ^ 2)O (nlogn)
Сортування виборуЗнаходить найменший елемент у колекції та ставить його на належне місце в кінці кожної ітераціїO (N ^ 2)O (N ^ 2)O (N ^ 2)
Сортування купиЕлементи сортуються шляхом побудови мінімальної купи або максимальної купи.O (nlogn)O (nlogn)O (nlogn)

Окрім методів сортування, наведених у наведеній вище таблиці, Java також підтримує такі методи сортування:

  • Відро Сортування
  • Сортування підрахунку
  • Сортування оболонки
  • Гребінець Сортування

Але ці прийоми економно використовуються в практичному застосуванні, тому ці прийоми не будуть частиною цієї серії.

Давайте обговоримо техніку сортування міхурів на Java.

Сортування міхура на Java

Сортування за бульбашками - найпростіший з усіх методів сортування в Java. Ця техніка сортує колекцію, неодноразово порівнюючи два сусідні елементи та міняючи місцями, якщо вони не у бажаному порядку. Таким чином, в кінці ітерації найважчий елемент набуває пухирців, щоб заявити про своє правильне положення.

Якщо в списку A є n елементів, заданих A (0), A (1), A (2), A (3),… .A (n-1), тоді A (0) порівнюється з A (1) ), A (1) порівнюється з A (2) тощо. Після порівняння, якщо перший елемент більший за другий, два елементи поміняються місцями, якщо вони не в порядку.

Алгоритм сортування міхурів

Загальний алгоритм техніки сортування міхурів наведено нижче:

Крок 1: Для i = 0 до N-1 повторіть крок 2

Крок 2: Для J = i + 1 до N - повторюю

Крок 3: якщо A (J)> A (i)
Поміняти місцями A (J) та A (i)
(Кінець внутрішнього циклу для циклу)
(Завершити, якщо зовнішній цикл)

Крок 4: Вихід

Тепер продемонструємо техніку сортування міхурів на наочному прикладі.

Візьмемо масив розміром 5 і проілюструємо алгоритм сортування бульбашок.

Сортування масиву за допомогою сортування Bubble

Наступний список слід відсортувати.

список для сортування

Пройти 1

найкращий безкоштовний DVD ripper для зашифрованих DVD

Пройти 2

пройти 3

Як ви можете бачити вище, масив повністю відсортований.

Наведену вище ілюстрацію можна узагальнити у табличній формі, як показано нижче:

ПройтиНесортований списокпорівнянняВідсортований список
{3,6,11,4,15}{11.4}{3,6,4,11,15}
один{11, 3, 6,15,4}{11.3}{3,11,6,15,4}
{3,11,6,15,4}{11.6}{3,6,11,15,4}
{3,6,11,15,4}{11.15}{3,6,11,15,4}
{3,6,11,15,4}{15.4}{3,6,11,4,15}
два{3,6,11,4,15}{3,6}{3,6,11,4,15}
{3,6,11,4,15}{6.11}{3,6,11,4,15}
3{3,6,4,11,15}{3,6}{3,6,4,11,15}
{3,6,4,11,15}{6.4}{3,4,6,11,15}
{3,4,6,11,15}СОРТОВАНО

Як показано у наведеному вище прикладі, найбільший елемент бульбашить до свого належного положення з кожною ітерацією / проходом. Загалом, коли ми досягаємо N-1 (де N - загальна кількість елементів у списку) проходить; ми будемо сортувати весь список.

Приклад коду сортування міхурів

Наведена нижче програма показує реалізацію Java алгоритму сортування міхурів. Тут ми підтримуємо масив чисел і використовуємо два для циклів для обходу сусідніх елементів масиву. Якщо два сусідні елементи не в порядку, тоді вони поміняні місцями.

import java.util.*; class Main{ // Driver method to test above public static void main(String args()) { //declare an array of integers int intArray() = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println('Original array: ' + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i intArray(j+1)) { int temp = intArray(j); intArray(j) = intArray(j+1); intArray(j+1) = temp; } //print the sorted array System.out.println('Sorted array: ' + Arrays.toString(intArray)); } }

Вихід:

Оригінальний масив: (23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80)
Відсортований масив: (9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96)

5 вихід

Часті запитання

Q # 1) Що таке алгоритми сортування в Java?

Відповідь: Алгоритм сортування може бути визначений як алгоритм або процедура, за допомогою якої елементи в колекції можуть бути впорядковані або розташовані бажаним чином.

Нижче наведено деякі алгоритми сортування, що підтримуються на Java:

  • Сортування бульбашок
  • Сортування вставки
  • Сортування виділення
  • Сортувати злиття
  • Швидкий сорт
  • Сортування Radix
  • Теплий сорт

Q # 2) Який найкращий алгоритм сортування в Java?

Відповідь: Сортування злиття має бути найшвидшим алгоритмом сортування в Java. Насправді Java 7 використовувала злиття сортування для реалізації методу Collections.sort (). Швидке сортування - це ще один найкращий алгоритм сортування.

Q # 3) Що таке сортування міхурів у Java?

Відповідь: Сортування за міхурами - це найпростіший алгоритм на Java. Сортування за допомогою міхура завжди порівнює два сусідні елементи у списку та замінює їх місцями, якщо вони не в бажаному порядку. Таким чином, в кінці кожної ітерації або проходу найважчий елемент барботується до належного місця.

Q # 4) Чому Bubble сортує Nдва?

Відповідь: Для реалізації сортування бульбашок ми використовуємо два для циклів.

Як порівняти два файли в

Загальна виконана робота вимірюється:

Кількість робіт, виконаних внутрішнім циклом * загальна кількість запусків зовнішнього циклу.

Для списку з n елементів внутрішній цикл працює для O (n) для кожної ітерації. Зовнішній цикл працює для ітерації O (n). Отже, загальна виконана робота дорівнює O (n) * O (n) = O (nдва)

Q # 15) Які переваги сорту Bubble?

Відповідь: Переваги сортування бульбашок такі:

  1. Легко кодувати та розуміти.
  2. Для реалізації алгоритму потрібно декілька рядків коду.
  3. Сортування здійснюється на місці, тобто додаткова пам'ять не потрібна, а отже, не витрачається багато пам'яті.
  4. Відсортовані дані одразу доступні для обробки.

Висновок

Наразі ми обговорювали алгоритм сортування Bubble Sort на Java. Ми також дослідили алгоритм та детальну ілюстрацію сортування масиву за допомогою техніки сортування міхурів. Потім ми застосували програму Java до Bubble Sort.

У наступному підручнику ми продовжимо інші методи сортування в Java.

=> Перевірте ВСІ підручники Java тут.

Рекомендована література

^