Прямая вставка сортировки
Идея вставить напрямую сортировки легко понять, выглядит так:
1. Разделите массив, который будет отсортирован на две части: отсортировано и не сортируется. В начале первый элемент считается отсортированным.
2. Начните со второго элемента, найдите соответствующую позицию элемента в отсортированном Subarray и вставьте его.
3. Повторите приведенный выше процесс, пока последний элемент не вставлен в упорядоченный Subarray.
4. Сортировка завершена.
Пример:
Идея проста, но код не так просто написать, как сортировка пузырьков. Прежде всего, как определить правильную позицию? Больше или равна левой, меньше или равна правой? Нет, необходимо учитывать много граничных условий, и есть слишком много суждений. Во -вторых, вставка элементов в массив неизбежно потребует перемещения большого количества элементов. Как контролировать их движение?
На самом деле, это не проблема с самим алгоритмом, и это как -то связано с языком программирования. Иногда сам алгоритм уже очень зрелый, и он все еще должен быть немного изменен, когда речь идет о конкретном языке программирования. Мы говорим здесь, так это алгоритм Java, так что давайте поговорим о Java.
Чтобы решить вышеупомянутую проблему, мы сделали небольшую утонченность второго шага. Мы не начинаем сравнивать начальную позицию суб-апельсий, но начинаем обратное сравнение из хвоста под-арайла. Пока он больше, чем число, которое необходимо вставить, мы движемся назад. До тех пор, пока число не будет больше, чем число, то число, которое нужно вставить, будет помещен в это пустое положение. Поэтому мы можем написать следующий код:
Insertarray.java
открытый класс insertarray {// array private long [] arr; // размер действительных данных в массиве Private Intems; // конструктор по умолчанию public insertArray () {arr = new Long [50]; } public insertArray (int max) {arr = new long [max]; } // вставить данные public void insert (long value) {arr [elems] = value; elems ++; } // Показать данные public void display () {for (int i = 0; i <elems; i ++) {System.out.print (arr [i]+""); } System.out.println (); } // Вставьте сортировку public void insertsort () {long select = 0l; для (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; for (j = i; j> 0 && arr [j - 1]> = select; j--) {arr [j] = arr [j - 1]; } arr [j] = select; }}} Тестовый класс:
Testinsertarray.java
открытый класс TestinSertArray {public static void main (string [] args) {insertArray iarr = new insertArray (); Iarr.insert (85); Iarr.insert (7856); Iarr.insert (12); Iarr.insert (8); yarr.insert (5); Iarr.insert (56); yarr.display (); yarr.insertsort (); yarr.display (); }} Результат печати:
Производительность алгоритма/сложность
Теперь давайте обсудим сложность времени алгоритма прямого вставки. Независимо от ввода, алгоритм всегда выполняет раунды сортировки N-1. Однако, поскольку точка вставки каждого элемента неопределенна и сильно влияет на входные данные, его сложность не является определенной. Мы можем обсудить лучшие, худшие и средние ситуации.
1. Лучший случай: из характеристик алгоритма можно видеть, что когда массив должен быть расположен в положительном порядке (массив упорядочен, а порядок такой же, как и требуемый порядок, который находится в порядке возрастания в соответствии с нашей предпосылкой для обсуждения). Причина в том, что в этом случае каждый элемент должен сравниваться только один раз и не нужно перемещать. Временная сложность алгоритма - O (n);
2. В худшем случае: Очевидно, когда массив, который будет расположен в обратном порядке, это худший случай. В этом случае наше количество сравнений за раунд I-1, а количество заданий-это i. Общее количество раз-это сумма первых n членов серии 2n-1, то есть n^2. Временная сложность алгоритма составляет O (n^2);
3. Средняя ситуация. Из приведенного выше анализа мы можем получить, что количество операций алгоритма в соответствии с средней ситуацией составляет приблизительно (n^2)/2 (примечание. Расчет здесь основан на назначении и сравнении. Если он основан на движении и сравнении, это приблизительно n^2/4). Очевидно, что сложности времени все еще O (n^2).
Что касается пространственной сложности алгоритма, все движения выполняются внутри данных. Единственным накладным расходом является то, что мы представили временную переменную (некоторые структуры данных называются «Стражи» в книгах), поэтому ее пространственная сложность (дополнительное пространство) составляет O (1).
Стабильность алгоритма
Поскольку вам нужно только найти позицию, которая не превышает текущего числа, и вам не нужно обменять, вставить сортирование напрямую является стабильным методом сортировки.
Алгоритм варианты
Если нужно организовать много данных, то это будет вызывать много накладных расходов каждый раз, когда вы смотрите сзади на фронт. Чтобы улучшить скорость поиска, бинарный поиск может использоваться для оптимизации производительности. Поскольку эффективность бинарного поиска очень высока, обеспечивается сложность O (n), и эффективность поиска может быть значительно улучшена, когда есть больше данных, или входные данные имеют тенденцию быть в худшем случае. В некоторых книгах этот метод называется складыванием и наполовину вставкой сортировки. Его реализация кода довольно сложна и может быть опубликована, если у вас будет время в будущем.
Кроме того, существуют двухсторонние виды вставки и сортировки таблицы. Сорта с двусторонним вставкой дополнительно улучшается на основе складывания и половины вставки, и его количество движений значительно уменьшено, около n^2/8. Тем не менее, это не избегает количества движений и не снижает уровень сложности. Сортировка вставки таблицы полностью изменяет структуру хранения и не перемещает записи, но необходимо поддерживать связанный список, и указатель связанного списка изменен вместо перемещения записей. Следовательно, его сложность все еще O (n^2).
Для двухсторонней вставки и сортировки вставки таблицы вы можете обратиться к книге «Структура данных», под редакцией Яна Веймина и У Веймина.
Алгоритм применимых сценариев
Сортировка вставки не применима, когда массив большой из -за сложности O (n^2). Однако, когда есть относительно мало данных, это хороший выбор, обычно используемый в качестве расширения для быстрой сортировки. Например, в виде алгоритма STL и QSORT -алгоритма STDLIB сортировка вставки используется в качестве дополнения для быстрой сортировки и используется для сортировки небольшого количества элементов. Например, в реализации метода вида, используемого в JDK 7 java.util.arrays, когда длина массива, который будет отсортирован, меньше 47, будет использоваться сортировка вставки.