Содержание
Логика алгоритма сортировки вставки Java — один из многих простых вопросов, задаваемых в интервью . Он сортирует массив по одному элементу за раз . Очень эффективно для относительно небольшого и среднего набора массивов. Сортировка вставок не рекомендуется для большого набора массивов.
Взгляните на алгоритм Bubble Sort и Selection Sort для сравнения.
Логика сортировки вставок очень проста
На каждой итерации наименьший элемент будет добавлен в несортированный массив. Давайте рассмотрим этот сценарий.
- У вас есть 10 элементов в массиве.
- 1-я итерация помещает наименьший элемент в позицию 1. Мы назовем его как
sorted array, Оставшиеся 9 элементов назовем какunsorted array, - Теперь во 2-й итерации самый маленький элемент из несортированного массива будет помещен в 1-ю позицию. Теперь будет 2 элемента в отсортированном массиве и 8 элементов в несортированном массиве.
- Та же итерация будет продолжаться, пока мы не достигнем
0 elementв несортированном массиве.
Давайте начнем
- Создать класс
CrunchifyInsertionSortAlgorithm.java - Добавьте всего 11 элементов в массив
crunchifyArray - Сначала выведите несортированный массив
- Теперь сортируйте массив, используя
InsertionSortАлгоритм - После каждой итерации выведите массив Значение для отладки
- Распечатать окончательно отсортированный массив и проверить
Вот исходный код сортировки вставкой
CrunchifyInsertionSortAlgorithm.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
пакет crunchify. ком . учебник ;
/ **
* @author Crunchify.com
* Алгоритм сортировки вставок в Java
*
* /
общественности учебный класс CrunchifyInsertionSortAlgorithm {
общественности статический недействительным main ( Строка [ ] аргументы ) {
// Начнем с arraySize 11
ИНТ ARRAYSIZE знак равно 11 ;
CrunchifyInsertionSortArray crunchifyArray ;
crunchifyArray знак равно новый CrunchifyInsertionSortArray ( arraySize ) ;
crunchifyArray . вставить ( 10 ) ;
crunchifyArray . вставить ( 17 ) ;
crunchifyArray . вставить ( — 9 ) ;
crunchifyArray . вставить ( 1 ) ;
crunchifyArray . вставить ( 8 ) ;
crunchifyArray . вставить ( 33 ) ;
crunchifyArray . вставить ( 7 ) ;
crunchifyArray . вставить ( 35 ) ;
crunchifyArray . вставить ( 15 ) ;
crunchifyArray . вставить ( 21 ) ;
crunchifyArray . вставить ( 4 ) ;
Система. вне. print ( «Вот наш начальный массив:» ) ;
CrunchifyInsertionSortArray . log ( ) ;
CrunchifyInsertionSortArray . crunchifyInsertionSort ( ) ;
Система. вне. print ( «Вот наш окончательный массив после вставки sort:» ) ;
CrunchifyInsertionSortArray . log ( ) ;
}
}
/ **
* Алгоритм сортировки вставок
* /
учебный класс CrunchifyInsertionSortArray {
частный статический int [ ] crunchifyObject ;
частный статический ИНТ crunchifyIndex ; // Индекс по умолчанию равен 0
/ **
* Простой конструктор
* /
общественности CrunchifyInsertionSortArray ( int arraySize ) {
crunchifyObject знак равно новый int [ arraySize ] ;
crunchifyIndex знак равно 0 ;
}
/ **
* Вставьте массив
* /
общественности недействительным вставить ( int crunchifyValue ) {
crunchifyObject [ crunchifyIndex ++ ] знак равно crunchifyValue ;
}
/ **
* Acutal Insertion Sort Logic идет сюда …
* /
общественности статический недействительным crunchifyInsertionSort ( ) {
ИНТ tmpObj , obj1 , obj2 ;
// Счетчик для печати итерации
ИНТ счетчик знак равно 1 ;
за ( obj2 знак равно 1 ; obj2 < crunchifyObject . длина ; obj2 ++ ) {
obj1 знак равно obj2 — 1 ;
tmpObj знак равно crunchifyObject [ obj2 ] ;
в то время как ( ( obj1 > = 0 ) && (tmpObj
crunchifyObject [obj1 + 1] = crunchifyObject [obj1];
obj1 — ;
}
crunchifyObject [ obj1 + 1 ] знак равно tmpObj ;
// напечатаем массив после каждой итерации
журнал ( «Итерация» + счетчик ) ;
counter ++ ;
}
}
частный статический недействительным log ( Строка строка ) {
Система. вне. println ( ========= + строка + ========= ) ;
log ( ) ;
}
/ **
* Давайте отображать массив
* /
общественности статический недействительным журнал ( ) {
за ( int я знак равно 0 ; я < crunchifyIndex ; я ++ )
Система. вне. print ( crunchifyObject [ i ] + ) ;
Система. вне. println ( / n ) ;
}
}
|
Запустите вышеуказанную программу в Eclipse . Вы можете изменить целые значения , если вы хотите или использовать случайный метод для добавления элементов в целочисленный массив.
Пример выше java будет работать для вас, если у вас есть какие-либо из следующих вопросов:
- Написать программу для вставки сортировки в Java
- Реализация сортировки вставки в Java
- Java-программа для реализации вставки сортировки
Выход консоли Eclipse:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
Вот наш начальный массив : 10 17 — 9 1 8 33 7 35 15 21 4
========= итерация 1 =========
10 17 — 9 1 8 33 7 35 15 21 4
========= итерация 2 =========
— 9 10 17 1 8 33 7 35 15 21 4
========= итерация 3 =========
— 9 1 10 17 8 33 7 35 15 21 4
========= итерация 4 =========
— 9 1 8 10 17 33 7 35 15 21 4
========= итерация 5 =========
— 9 1 8 10 17 33 7 35 15 21 4
========= итерация 6 =========
— 9 1 7 8 10 17 33 35 15 21 4
========= итерация 7 =========
— 9 1 7 8 10 17 33 35 15 21 4
========= итерация 8 =========
— 9 1 7 8 10 15 17 33 35 21 4
========= итерация 9 =========
— 9 1 7 8 10 15 17 21 33 35 4
========= итерация 10 =========
— 9 1 4 7 8 10 15 17 21 33 35
Вот наш финал массив после вставки сортировать : — 9 1 4 7 8 10 15 17 21 33 35
|
0.00 (0%) 0 votes
