Алгоритм сортировки вставками в Java с примером программы
⚡ Умное резюме
Сортировка вставками Java Эта функция формирует отсортированный раздел массива по одному элементу за раз, сдвигая большие значения вправо до тех пор, пока каждый ключ не окажется на своей правильной позиции, что делает ее идеальной для небольших наборов данных.
Что такое алгоритм сортировки вставками?
Сортировка вставками — это простой алгоритм сортировки, подходящий для небольших наборов данных. На каждой итерации алгоритм:
- Удаляет элемент из массива.
- Сравнивает его с наибольшим значением в массив.
- Перемещает элемент в правильное место.
Поведение алгоритма напоминает то, как игрок в карты раскладывает карты: каждая новая карта берётся и сдвигается влево мимо каждой более крупной карты, пока не окажется на нужном месте. Поскольку все сдвиги происходят внутри исходного массива, сортировка вставками является одновременно и сортировкой на месте, и стабильной.
Он относится к тому же семейству товаров, подходящих для начинающих. Java процедуры сортировки как пузырьковая сортировкаОднако при этом обычно выполняется гораздо меньше операций записи в данные, которые уже частично упорядочены.
Процесс алгоритма сортировки вставками
Вот как графически работает алгоритм сортировки вставками:

Анимация повторяет те же три шага. Java Приведенная ниже программа выполняет следующие действия. Таблица тестового запуска. tracПрограмма выполняет эти шаги на примере массива {860, 8, 200, 9} точно так, как программа выводит их во время выполнения.
| Проходить | Ключевой элемент | Проведены сравнения | Массив после прохода |
|---|---|---|---|
| 1 | 8 | 8 против 860 | 8 860 200 9 |
| 2 | 200 | 200 против 860 | 8 200 860 9 |
| 3 | 9 | 9 против 860, затем 9 против 200 | 8 9 200 860 |
Обратите внимание, что на третьем этапе требуется два сравнения, поскольку ключ 9 должен пройти мимо двух больших значений. Следовательно, количество сравнений увеличивается пропорционально тому, насколько сильно каждый элемент начинает смещаться относительно своего первоначального порядка.
Java Пример программы для сортировки массива с использованием алгоритма сортировки вставками:
Приведённая ниже программа сортирует массив {860, 8, 200, 9} и выводит комментарий к нему, так что каждое сравнение и каждый сдвиг видны. Сохраните её как InsertionSortExample.java и скомпилировать его с любой версией JDK 8 или более поздней.
package com.guru99; public class InsertionSortExample { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("Before Insertion Sort"); printArray(myArray); insertionSort(myArray);//sorting array using insertion sort System.out.println("After Insertion Sort"); printArray(myArray); } public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; i++) { System.out.println("Sort Pass Number "+(i)); int key = arr[i]; int j = i-1; while ( (j > -1) && ( arr [j] > key ) ) { System.out.println("Comparing "+ key + " and " + arr [j]); arr [j+1] = arr [j]; j--; } arr[j+1] = key; System.out.println("Swapping Elements: New Array After Swap"); printArray(arr); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Запуск класса приводит к следующему результату: tracЗдесь показано каждое. Номер сортировочного пропуска Эта строка обозначает одну итерацию внешнего цикла, а строка, выводимая после каждой замены, показывает состояние массива в данный момент.
Code Выход:
Before Insertion Sort 860 8 200 9 Sort Pass Number 1 Comparing 8 and 860 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 200 860 9 Sort Pass Number 3 Comparing 9 and 860 Comparing 9 and 200 Swapping Elements: New Array After Swap 8 9 200 860 After Insertion Sort 8 9 200 860
Временная и пространственная сложность сортировки вставками
Производительность сортировки вставками в значительной степени зависит от степени упорядоченности входных данных, поэтому наилучший и наихудший случаи различаются на целый порядок роста.
| Кейсы | Условие ввода | Сложность времени |
|---|---|---|
| лучший | Массив уже отсортирован, поэтому внутренний цикл while никогда не запускается. | О (п) |
| Средняя | Элементы поступают в случайном порядке. | O (n²) |
| Наихудший | Массив отсортирован в обратном порядке, поэтому каждый ключ перемещается в начало. | O (n²) |
Использование пространства значительно упрощено. Только прилавки. i, j, n и key создаются, и массив перестраивается на месте, поэтому вспомогательное пространство имеет размер O(1) независимо от того, насколько велики входные данные.
Поскольку внутренний цикл останавливается, как только встречает меньшее значение, сортировка вставками описывается как адаптивная: чем ближе входные данные к отсортированному порядку, тем ближе время выполнения к линейному.
Преимущества и недостатки сортировки вставками
Сортировка вставками сохраняется в производственных библиотеках, несмотря на случай квадратичного среднего, потому что её постоянные множители малы, а поведение предсказуемо.
Преимущества
- Простой в написании и лёгкий в исполнении. tracнаписанный от руки, что делает его подходящим для преподавания и проведения собеседований.
- Стабильность обеспечивает сохранение исходного относительного порядка записей, имеющих общий ключ.
- На месте требуется всего O(1) дополнительной памяти помимо входного массива.
- Адаптивный алгоритм, достигающий сложности O(n) на данных, которые уже почти отсортированы.
- Это означает, что сортировка списка возможна даже при поступлении новых элементов.
Недостатки
- Квадратичная сложность вычислений на случайных или обратных входных данных делает этот метод непригодным для больших массивов.
- Каждый сдвиг записывает данные в массив, поэтому он перемещает больше данных, чем сортировка выбором.
- Сортировка слиянием и быстрая сортировка значительно превосходят его по производительности, как только на входе появляется несколько десятков элементов.
Практическое правило заключается в том, чтобы использовать сортировку вставками, когда массив невелик, когда данные почти упорядочены или когда сортировка методом «разделяй и властвуй» сократила раздел до нескольких элементов.
Сортировка вставками против Bubble-сортировка против сортировки выбором
Все три алгоритма используют квадратичную сортировку сравнением, однако они различаются по стабильности, по тому, как реагируют на упорядоченные входные данные, и по количеству выполняемых операций записи.
| Критерии | Сортировка вставки | Bubblэлектронная сортировка | Выбор сортировки |
|---|---|---|---|
| лучший случай | О (п) | O(n) с флагом досрочного выхода | O (n²) |
| Средний и наихудший сценарий | O (n²) | O (n²) | O (n²) |
| Дополнительное пространство | O (1) | O (1) | O (1) |
| Стабильный | Да | Да | Нет, в стандартной версии массива. |
| Адаптивный | Да | Да, при использовании оптимизации флагов. | Нет |
| Записывает данные в массив. | Много смен, мало данных, полученных в упорядоченном виде. | Много обменов | ровно n-1 обменов |
Сортировка выбором выигрывает, когда запись обходится дорого, потому что она выполняет наименьшее количество обменов. Сортировка вставками выигрывает почти везде в этом масштабе, особенно на частично упорядоченных данных, поэтому библиотечные сортировки, такие как та, что используется в данном случае, выигрывают. общий Java упражнения А внутренние компоненты JDK переключаются на него для очень маленьких разделов.
