Содержание
Bubble sort иногда неправильно обозначается как sinking sort , — это простой алгоритм сортировки , который работает путем многократного пошагового перемещения по списку для сортировки, сравнения каждой пары смежных элементов и их замены, если они находятся в неправильном порядке.
Проход по списку повторяется до тех пор, пока не понадобятся никакие подкачки , что указывает на то, что список отсортирован. Алгоритм получил свое название от того, как меньшие элементы bubble наверх списка.
Поскольку он использует только сравнения для работы с элементами, это сортировка сравнения. Хотя алгоритм прост, большинство других алгоритмов сортировки более эффективны для больших списков.
Логика проста:
При сортировке по пузырькам мы в основном пересекаем массив с первой позиции (размер — 1) и сравниваем элемент со следующей. Поменяйте элемент со следующим элементом, только если следующий элемент больше.
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
|
пакет crunchify. ком . учебные пособия ;
Импортировать Java. Util. Массивы ;
/ **
* @author Crunchify.com.
* Как реализовать алгоритм сортировки пузырьков в Java? Учебник по возрастанию и убыванию
* /
общественности учебный класс CrunchifyBubbleSort {
общественности статический недействительным main ( Строка [ ] аргументы ) {
ИНТ crunchifyArry [ ] знак равно { 15 , 3 , 9 , 7 , 19 , 8 , 1 , 5 } ;
log ( «Давайте начнем с реализации Bubble Sort в Java / n» ) ;
log ( ============ Результат по возрастанию: + Массивы . toString ( CrunchifyBubbleSortAsceMethod ( crunchifyArry ) ) + / n ) ;
log ( ============ Результат по убыванию: + Массивы . toString ( CrunchifyBubbleSortDescMethod ( crunchifyArry ) ) + / n ) ;
}
// Алгоритм пузырьковой сортировки по возрастанию
общественности статический int [ ] CrunchifyBubbleSortAsceMethod ( int [ ] crunchifyArr ) {
ИНТ темп ;
за ( int я знак равно 0 ; я < crunchifyArr . длина — 1 ; я ++ ) {
за ( int J знак равно 1 ; J < crunchifyArr . длина — я ; j ++ ) {
если ( crunchifyArr [ j — 1 ] > crunchifyArr [ j ] ) {
температура знак равно crunchifyArr [ j — 1 ] ;
crunchifyArr [ j — 1 ] знак равно crunchifyArr [ j ] ;
crunchifyArr [ j ] знак равно темп ;
}
}
журнал ( «Итерация» + ( я + 1 ) + : + Массивы . toString ( crunchifyArr ) ) ;
}
вернуть crunchifyArr ;
}
// Алгоритм сортировки пузырьков в порядке убывания
общественности статический int [ ] CrunchifyBubbleSortDescMethod ( int [ ] crunchifyArr ) {
ИНТ темп ;
за ( int я знак равно 0 ; я < crunchifyArr . длина — 1 ; я ++ ) {
за ( int J знак равно 1 ; J < crunchifyArr . длина — я ; j ++ ) {
если ( crunchifyArr [ j — 1 ] < crunchifyArr [ j ] ) {
температура знак равно crunchifyArr [ j — 1 ] ;
crunchifyArr [ j — 1 ] знак равно crunchifyArr [ j ] ;
crunchifyArr [ j ] знак равно темп ;
}
}
журнал ( «Итерация» + ( я + 1 ) + : + Массивы . toString ( crunchifyArr ) ) ;
}
вернуть crunchifyArr ;
}
// Простой лог утилита
частный статический недействительным log ( Строка результат ) {
Система. вне. println ( результат ) ;
}
}
|
Результат Eclipse Console
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
Давайте начать работу по реализации Bubble Sort в Джава
итерация 1 : [ 3 , 9 , 7 , 15 , 8 , 1 , 5 , 19 ]
итерация 2 : [ 3 , 7 , 9 , 8 , 1 , 5 , 15 , 19 ]
итерация 3 : [ 3 , 7 , 8 , 1 , 5 , 9 , 15 , 19 ]
итерация 4 : [ 3 , 7 , 1 , 5 , 8 , 9 , 15 , 19 ]
итерация 5 : [ 3 , 1 , 5 , 7 , 8 , 9 , 15 , 19 ]
итерация 6 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
итерация 7 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
============ Восходящий результат заказа: [1, 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
итерация 1 : [ 3 , 5 , 7 , 8 , 9 , 15 , 19 , 1 ]
итерация 2 : [ 5 , 7 , 8 , 9 , 15 , 19 , 3 , 1 ]
итерация 3 : [ 7 , 8 , 9 , 15 , 19 , 5 , 3 , 1 ]
итерация 4 : [ 8 , 9 , 15 , 19 , 7 , 5 , 3 , 1 ]
итерация 5 : [ 9 , 15 , 19 , 8 , 7 , 5 , 3 , 1 ]
итерация 6 : [ 15 , 19 , 9 , 8 , 7 , 5 , 3 , 1 ]
итерация 7 : [ 19 , 15 , 9 , 8 , 7 , 5 , 3 , 1 ]
============ Результат по убыванию Сортировать: [19, 15 , 9 , 8 , 7 , 5 , 3 , 1 ]
|
Что такое временная сложность алгоритма пузырьковой сортировки?
- Если вы считаете,
Best caseсценарий тогда было быO(n) - Если вы считаете,
Worst caseсценарий тогда было быO(n2)
0.00 (0%) 0 votes
