Введение в сортировку вставок в Java
Если вы программист, вы наверняка уже много слышали о сортировке. Сортировка - это расположение элементов по возрастанию или по убыванию. Существует так много алгоритмов сортировки, доступных для сортировки элементов, и каждый алгоритм имеет разные способы сортировки, разную сложность. Таким образом, это зависит от конкретного сценария и количества элементов относительно того, какой алгоритм следует использовать. Вставка также является одним из обычно используемых алгоритмов сортировки, в целом имеющих сложность O (n 2), и выполняется так, как будто мы сортируем игральные карты в наших руках. В этой теме мы собираемся узнать о сортировке вставок в Java.
Как вставка сортировки работает в Java?
Давайте разберемся в работе сортировки вставок на примере. Предположим, что есть массив с именем arr, имеющий следующие элементы:
10 5 8 20 30 2 9 7
Шаг # 1 - сортировка вставки начинается со 2-го элемента массива, то есть с 5, учитывая 1-й элемент массива, отсортированный сам по себе Теперь элемент 5 сравнивается с 10, поскольку 5 меньше 10, поэтому 10 перемещается на 1 позицию вперед, а 5 вставляется перед ним.
Теперь результирующий массив:
5 10 8 20 30 2 9 7
Шаг № 2 - Теперь элемент arr (2), т. Е. 8, сравнивается с элементом arr (1), т. Е. 10. Поскольку 8 меньше, чем его предыдущий элемент 10, он сдвигается на один шаг вперед от своей позиции, а затем он по сравнению с 5. Так как 8 больше 5, поэтому он вставляется после него.
Тогда результирующий массив:
5 8 10 20 30 2 9 7
Шаг № 3 - Теперь элемент 20 сравнивается с 10, поскольку он больше 10, он остается на своем месте.
5 8 10 20 30 2 9 7
Шаг № 4 - Элемент 30 сравнивается с 20, и, поскольку он больше 20, никаких изменений не будет, и массив останется таким, как есть. Теперь массив будет
5 8 10 20 30 2 9 7
Шаг № 5 - Элемент 2 сравнивается с 30, так как он меньше 30, он сдвигается на одну позицию вперед, затем он сравнивается с 20, 10, 8, 5, один за другим, и все элементы сдвигаются на 1 позицию вперед и 2 вставляется до 5.
Полученный массив:
2 5 8 10 20 30 9 7
Шаг № 6 - Элемент 9 сравнивается с 30, поскольку он меньше 30, он сравнивается с 20, 10 один за другим, и элемент сдвигается на 1 позицию вперед, а 9 вставляется до 10 и после 8. В результате получается массив:
2 5 8 9 10 20 30 7
Шаг № 7 - Элемент 7 сравнивается с 30, а поскольку он меньше 30, он сравнивается с 30, 20, 10, 9, 8, и все элементы сдвигаются на 1 позицию вперед один за другим, а 7 вставляется до 8 Полученный массив станет:
2 5 7 8 9 10 20 30
Таким образом, все элементы массива сортируются с использованием сортировки вставкой, начиная сравнение с предыдущим элементом.
Примеры реализации сортировки вставками в Java
Вставная сортировка в Java - это простой алгоритм сортировки, подходящий для всех небольших наборов данных.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Выход:
12 15 18 21 23 52 61
Объяснение:
В приведенной выше программе Insertion Sort функция inserttionSort () используется для сортировки элементов исходного массива. Сортировка начинается со второго элемента, поскольку первый элемент считает отсортированным сам по себе. Таким образом, цикл 'j' начинается с индекса 1 массива. «i» - это переменная, отслеживающая индекс непосредственно перед «j» для сравнения значения. key '- это переменная, содержащая значение текущего элемента, который должен быть расположен в отсортированной позиции. Цикл while () выполняется, если текущее значение меньше, чем крайнее левое значение, так что смещение элементов может быть обработано, и в конце можно вставить текущий элемент в правильное положение. Функция printArray () используется для окончательной печати отсортированного массива.
1. Лучший случай
В сортировке вставки лучший случай был бы, когда все элементы массива уже отсортированы. Поэтому, когда любой элемент сравнивается с его крайним левым элементом, он всегда больше и, следовательно, не будет обрабатываться смещение и вставка элементов. В этом случае наилучшая сложность будет линейной, т.е. O (n).
2. Худший случай
В приведенном выше коде сортировки вставки наихудший случай был бы, когда массив находится в обратном порядке, поэтому каждый раз, когда элемент сравнивается с его крайним левым элементом, он всегда меньше и затем сравнивается со всеми имеющимися исходящими элементами и смещением и вставка сделана. В этом случае сложность сортировки вставки O (n 2).
3. Средний случай
Даже в среднем случае сортировка вставкой имеет сложность O (n 2), при которой некоторые элементы не требуют смещения, тогда как некоторые элементы смещены со своих позиций, и вставка выполняется в правильном положении.
4. Лучшее использование
Сортировку вставкой лучше всего использовать, когда размер массива не очень велик, или нужно отсортировать только небольшое количество элементов, в которых отсортированы почти все элементы и необходимо внести только некоторые изменения. Сортировка вставкой - один из самых быстрых алгоритмов для массива небольшого размера, даже быстрее, чем Быстрая сортировка Фактически, быстрая сортировка использует сортировку вставки при сортировке своих небольших частей массива.
Вывод
Приведенное выше объяснение ясно показывает работу и реализацию Insertion Sort в Java. В других языках программирования логика выполнения сортировки вставками остается той же самой, только изменения синтаксиса. Перед реализацией любого алгоритма сортировки очень важно провести некоторый анализ сценария, в котором необходимо выполнить сортировку, поскольку не каждый алгоритм сортировки подходит для всех сценариев.
Рекомендуемые статьи
Это руководство по сортировке вставок в Java. Здесь мы обсуждаем, как сортировка вставкой работает в Java с Примерами, чтобы Реализовать Сортировку вставкой в Java. Вы также можете взглянуть на следующие статьи, чтобы узнать больше -
- Квадратный корень на Яве
- BorderLayout в Java
- Обратный номер в Java
- StringBuffer в Java
- Квадратный корень в PHP
- Квадратный корень в JavaScript
- Руководство к 6 лучшим алгоритмам сортировки в Python