Содержание
На Crunchify мы уже написали 500+ Java and Spring MVC связанные с технологией учебники . Изучение новых вещей никогда не надоедало мне. Мне нравится изучать новые вещи каждый день, и я считаю, что это то же самое для моих читателей :).
Как вы, возможно, видели ранее, алгоритм пузырьковой сортировки, алгоритм сортировки выбора и алгоритм сортировки вставкой очень популярен среди различных интервью.
В этом уроке мы рассмотрим Merge Sort Algorithm ,
Алгоритм сортировки слиянием очень прост. Разделите массив на половину, когда он достигнет только одного уровня, затем сортируйте его. Следующий шаг — объединить его в последовательности . В основном это divide and conquer подход.
Вот простое объяснение сортировки слиянием о том, как ей разделить и объединить элементы.
Давайте ответим на все нижеуказанные вопросы сегодня в этом уроке:
- Что такое алгоритм сортировки слиянием?
- Какова реализация слияния?
- Слияние в Java — Учебное пособие
- сортировка слиянием java-код
Мы собираемся выполнить следующие шаги:
- Создайте
crunchifyArrayс размером 10 - Заполните 10 случайных чисел в массив
- Распечатать начальный массив
- Выполнить сортировку слиянием
- Печать окончательного массива после сортировки слиянием
Вот код Java:
CrunchifyMergeSortAlgorithm.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
|
пакет crunchify. ком . учебник ;
импорт Java . Util. * ;
/ **
* @author Crunchify.com Алгоритм сортировки слиянием в Java
*
* /
общественности учебный класс CrunchifyMergeSortAlgorithm {
общественности статический Целое число [ ] crunchifyArray знак равно новый Целое число [ 10 ] ; ;
общественности статический ИНТ итерация знак равно 1 ;
// Делим и объединяем
общественности статический недействительным crunchifyMergeSort ( Integer [ ] crunchifyArray ) {
Целое число [ ] tempArray знак равно новый Integer [ crunchifyArray . длина ] ;
// рекурсивно выполнить сортировку слиянием
crunchifyMergeSort ( crunchifyArray , tempArray , 0 , crunchifyArray . длина — 1 ) ;
}
// Идея проста:
// Сначала делим весь массив на 2 части
// Делим каждый массив на 2 части
// Как только он достигает только 1 элемента в каждом боковом дереве, просто сортируем его
// Сливаем назад таким же образом, чтобы получить полный отсортированный массив
частный статический недействительным crunchifyMergeSort ( Integer [ ] crunchifyArray , Целое число [ ] tempArray , ИНТ myLeft , ИНТ мой правый ) {
если ( myLeft < мой правый ) {
ИНТ центр знак равно ( myLeft + мой правый ) / 2 ;
crunchifyMergeSort ( crunchifyArray , tempArray , myLeft , центр ) ;
crunchifyMergeSort ( crunchifyArray , tempArray , центр + 1 , myRight ) ;
crunchifyMerge ( crunchifyArray , tempArray , myLeft , центр + 1 , myRight ) ;
}
}
// алгоритм сортировки слиянием
частный статический недействительным crunchifyMerge ( Integer [ ] crunchifyArray , Целое число [ ] tempArray , ИНТ слева , ИНТ мой правый ,
ИНТ RightMost ) {
ИНТ leftEnd знак равно мое право — 1 ;
ИНТ К знак равно слева ;
ИНТ Num знак равно самый правый — оставил + 1 ;
в то время как ( слева < = leftEnd && myRight <= rightMost)
if (crunchifyArray [left] .compareTo (crunchifyArray [myRight]) <= 0)
tempArray [k ++] = crunchifyArray [left ++];
еще
tempArray [ k ++ ] знак равно crunchifyArray [ myRight ++ ] ;
в то время как ( слева < = leftEnd )
tempArray [ k ++ ] знак равно crunchifyArray [ left ++ ] ;
в то время как ( myRight < = RightMost )
tempArray [ k ++ ] знак равно crunchifyArray [ myRight ++ ] ;
за ( int я знак равно 0 ; я < число ; я ++ , правоМост — )
crunchifyArray [ rightMost ] знак равно tempArray [ rightMost ] ;
Система. вне. print ( Итерация # + итерация + ===> ) ;
crunchifyPrint ( ) ;
итерация ++ ;
}
// Получить случайное целое число в Java
общественности статический целое число getRandomIntegers ( ) {
Случайный crunchifyRandom знак равно новый Случайный ( ) ;
ИНТ мой номер знак равно crunchifyRandom . следующий ( 150 ) ;
вернуть myNumber ;
}
// Просто печатать массивы
общественности статический недействительным crunchifyPrint ( ) {
за ( int N : crunchifyArray ) {
Система. вне. печать ( + N + ) ;
}
Система. вне. печать ( / n ) ;
}
// Основной метод
общественности статический недействительным main ( Строка [ ] аргументы ) {
за ( int я знак равно 0 ; я < crunchifyArray . длина ; я ++ ) {
crunchifyArray [ i ] знак равно getRandomIntegers ( ) ;
}
Система. вне. print ( «Вот наш начальный массив:» ) ;
crunchifyPrint ( ) ;
Система. вне. println ( ) ;
// Выполнить фактическую сортировку
crunchifyMergeSort ( crunchifyArray ) ;
Система. вне. println ( ) ;
Система. вне. print ( Вот массив после Merge Sort: ) ;
crunchifyPrint ( ) ;
}
}
|
Выход консоли Eclipse:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Вот наш начальный массив : 45 53 10 50 48 8 106 77 44 108
итерация # 1 ===> 45 53 10 50 48 8 106 77 44 108
итерация # 2 ===> 10 45 53 50 48 8 106 77 44 108
итерация # 3 ===> 10 45 53 48 50 8 106 77 44 108
итерация # 4 ===> 10 45 48 50 53 8 106 77 44 108
итерация # 5 ===> 10 45 48 50 53 8 106 77 44 108
итерация # 6 ===> 10 45 48 50 53 8 77 106 44 108
итерация # 7 ===> 10 45 48 50 53 8 77 106 44 108
итерация # 8 ===> 10 45 48 50 53 8 44 77 106 108
итерация # 9 ===> 8 10 44 45 48 50 53 77 106 108
Вот массив после сортировки слиянием : 8 10 44 45 48 50 53 77 106 108
|
Попробуйте отладить программу внимательно, чтобы понять два метода crunchifyMergeSort а также crunchifyMerge , Дайте мне знать, если у вас есть какие-либо вопросы или проблемы с запуском кода выше.
Big O Notation / Что такое сложность алгоритма сортировки слиянием?
n*log(n)
Сортировка Сортировка Сложность сценария в лучшем случае?
O(n)в случае уже отсортированного ввода
0.00 (0%) 0 votes
