Алгоритм сортировки вставками в Java с примером программы

⚡ Умное резюме

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

  • 🔘 Определение: Сортировка вставками удаляет один элемент и вставляет его на правильное место в отсортированном участке.
  • ☑️ Процесс: При каждом проходе ключ сравнивается с предыдущими значениями, а большие значения сдвигаются на одну позицию вправо.
  • ✅ Программа: Java В примере сортируются числа {860, 8, 200, 9}, и выводятся результаты каждого сравнения и обмена.
  • 🧪 Сложность: В лучшем случае выполнение программы занимает O(n) времени, в то время как в среднем и худшем случаях достигается O(n²).
  • 🇧🇷 Память: Сортировка происходит на месте, поэтому вспомогательное пространство остается O(1) для любого размера массива.
  • 📊 Поведение: Алгоритм стабилен и адаптивен, поэтому обработка почти отсортированных массивов завершается после очень небольшого количества сдвигов.

Алгоритм сортировки вставками в Java

Что такое алгоритм сортировки вставками?

Сортировка вставками — это простой алгоритм сортировки, подходящий для небольших наборов данных. На каждой итерации алгоритм:

  • Удаляет элемент из массива.
  • Сравнивает его с наибольшим значением в массив.
  • Перемещает элемент в правильное место.

Поведение алгоритма напоминает то, как игрок в карты раскладывает карты: каждая новая карта берётся и сдвигается влево мимо каждой более крупной карты, пока не окажется на нужном месте. Поскольку все сдвиги происходят внутри исходного массива, сортировка вставками является одновременно и сортировкой на месте, и стабильной.

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

Процесс алгоритма сортировки вставками

Вот как графически работает алгоритм сортировки вставками:

анимационный trace алгоритма сортировки вставками, переупорядочивающего несортированный список
Процесс алгоритма сортировки вставками

Анимация повторяет те же три шага. 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 переключаются на него для очень маленьких разделов.

Часто задаваемые вопросы (FAQ)

Первый элемент сам по себе уже представляет собой отсортированный подмассив длиной в один элемент. Начиная с индекса 1, цикл всегда имеет, с чем сравнивать, поэтому ключ в позиции i вставляется в упорядоченный блок слева от него.

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

Да. Второй пилот GitHub Выполняет стандартную сортировку вставками на основе сигнатуры метода или комментария. RevПроверьте граничные условия самостоятельно, поскольку в сгенерированных циклах иногда используется j >= 0 или j > -1, что противоречит окружающему коду.

Бинарная сортировка вставками находит точку вставки с помощью бинарного поиска вместо линейного сканирования, сокращая количество сравнений для каждого элемента с O(n) до O(log n). Работа по сдвигу остается неизменной, поэтому общая временная сложность остается O(n²).

Да. Рекурсивная версия сортирует первые n-1 элементов, а затем вставляет последний элемент в отсортированный префикс. Она соответствует итеративной временной сложности, но добавляет пространство стека O(n), поэтому на практике предпочтительнее использовать версию с циклом.

Частично. Двойная сортировка с опорными элементами, используемая для примитивных типов данных, при очень малых разбиениях переключается на сортировку вставками, а TimSort, используемый для объектов, сортирует короткие последовательности с помощью бинарной сортировки вставками перед их слиянием.

Часто встречающиеся ошибки заключаются в начале внешнего цикла с 0, записи arr[j] = key вместо arr[j+1] = key, а также в пропуске условия j > -1, что приводит к возникновению исключения ArrayIndexOutOfBoundsException, когда ключ должен находиться в нулевой позиции.

Да. Замените проверку "больше" на compareTo для типа Comparable или на вызов Comparator. Логика сдвига останется неизменной, а стабильность сохранится, что важно, когда объекты используют один и тот же ключ сортировки.

Подведем итог этой публикации следующим образом: