Implémentation de l'algorithme de tri de fusion Java ? Explication détaillée et tutoriel complet

Publié: 2021-01-20
Implémentation de l'algorithme de tri de fusion Java ? Explication détaillée et tutoriel complet

Sur Crunchify, nous avons écrit jusqu'à présent plus de 500 tutoriels liés à la technologie 500+ Java and Spring MVC . Apprendre de nouvelles choses ne m'a jamais ennuyé. J'aime apprendre de nouvelles choses tous les jours et je pense qu'il en est de même pour mes lecteurs :).

Comme vous l'avez peut-être déjà vu, l'algorithme de tri à bulles, l'algorithme de tri par sélection et l'algorithme de tri par insertion sont très populaires parmi diverses interviews.

Dans ce tutoriel, nous allons passer en revue Merge Sort Algorithm .

L'algorithme de tri par fusion est très simple. Divisez un tableau en deux lorsqu'il n'atteint qu'un seul niveau, puis triez-le. L'étape suivante consiste à le fusionner en séquence. Fondamentalement, c'est l'approche divide and conquer .

Voici une explication simple sur le tri par fusion sur la façon dont il divisera et fusionnera des éléments.

Répondons à toutes les questions ci-dessous aujourd'hui dans ce tutoriel :

  • Qu'est-ce que l'algorithme de tri par fusion ?
  • Quelle est la mise en œuvre de la fusion ?
  • Fusionner en Java - Tutoriel
  • fusionner le code java de tri

Nous allons effectuer les étapes ci-dessous :

  1. Créer crunchifyArray avec la taille 10
  2. Remplir 10 entiers aléatoires dans un tableau
  3. Imprimer le tableau initial
  4. Effectuer un tri par fusion
  5. Imprimer le tableau final après le tri par fusion

Voici un code 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
package crunchify . com . tutorial ;
 
import java . util . * ;
 
/**
* @author Crunchify.com Merge Sort Algorithm in Java
*
*/
 
public class CrunchifyMergeSortAlgorithm {
public static Integer [ ] crunchifyArray = new Integer [ 10 ] ; ;
public static int iteration = 1 ;
 
// Divide and Merge
public static void crunchifyMergeSort ( Integer [ ] crunchifyArray ) {
Integer [ ] tempArray = new Integer [ crunchifyArray . length ] ;
 
// recursively perform merge sort
crunchifyMergeSort ( crunchifyArray , tempArray , 0 , crunchifyArray . length - 1 ) ;
 
}
 
// Idea is simple:
// First divide whole array into 2 part
// Divide each array into another 2 part
// Once it reaches to only 1 elements in each side tree, just sort it
// Merge backward the same way to get complete sorted array
private static void crunchifyMergeSort ( Integer [ ] crunchifyArray , Integer [ ] tempArray , int myLeft , int myRight ) {
 
if ( myLeft < myRight ) {
int center = ( myLeft + myRight ) / 2 ;
crunchifyMergeSort ( crunchifyArray , tempArray , myLeft , center ) ;
crunchifyMergeSort ( crunchifyArray , tempArray , center + 1 , myRight ) ;
crunchifyMerge ( crunchifyArray , tempArray , myLeft , center + 1 , myRight ) ;
}
}
 
// Merge Sort Algorithm
private static void crunchifyMerge ( Integer [ ] crunchifyArray , Integer [ ] tempArray , int left , int myRight ,
int rightMost ) {
int leftEnd = myRight - 1 ;
int k = left ;
int num = rightMost - left + 1 ;
 
while ( left < = leftEnd && myRight <= rightMost)
if (crunchifyArray[left].compareTo(crunchifyArray[myRight]) <= 0)
tempArray[k++] = crunchifyArray[left++];
else
tempArray [ k ++ ] = crunchifyArray [ myRight ++ ] ;
 
while ( left < = leftEnd )
tempArray [ k ++ ] = crunchifyArray [ left ++ ] ;
 
while ( myRight < = rightMost )
tempArray [ k ++ ] = crunchifyArray [ myRight ++ ] ;
 
for ( int i = 0 ; i < num ; i ++ , rightMost -- )
crunchifyArray [ rightMost ] = tempArray [ rightMost ] ;
 
System . out . print ( "Iteration # " + iteration + " ===> " ) ;
crunchifyPrint ( ) ;
iteration ++ ;
 
}
 
// Get Random Integer in Java
public static Integer getRandomIntegers ( ) {
 
Random crunchifyRandom = new Random ( ) ;
int myNumber = crunchifyRandom . nextInt ( 150 ) ;
return myNumber ;
}
 
// Simply Print Arrays
public static void crunchifyPrint ( ) {
for ( int n : crunchifyArray ) {
System . out . print ( " " + n + "  " ) ;
}
System . out . print ( "\n" ) ;
}
 
// Main Method
public static void main ( String [ ] args ) {
 
for ( int i = 0 ; i < crunchifyArray . length ; i ++ ) {
crunchifyArray [ i ] = getRandomIntegers ( ) ;
}
 
System . out . print ( "Here is our initial array: " ) ;
crunchifyPrint ( ) ;
System . out . println ( ) ;
 
// Perform actual sorting
crunchifyMergeSort ( crunchifyArray ) ;
 
System . out . println ( ) ;
System . out . print ( "Here is an array after Merge Sort: " ) ;
crunchifyPrint ( ) ;
}
}

Sortie de la console Eclipse :

1
2
3
4
5
6
7
8
9
10
11
12
13
Here is our initial array :    45    53    10    50    48    8    106    77    44    108   
 
Iteration # 1 ===>  45   53   10   50   48   8   106   77   44   108  
Iteration # 2 ===>  10   45   53   50   48   8   106   77   44   108  
Iteration # 3 ===>  10   45   53   48   50   8   106   77   44   108  
Iteration # 4 ===>  10   45   48   50   53   8   106   77   44   108  
Iteration # 5 ===>  10   45   48   50   53   8   106   77   44   108  
Iteration # 6 ===>  10   45   48   50   53   8   77   106   44   108  
Iteration # 7 ===>  10   45   48   50   53   8   77   106   44   108  
Iteration # 8 ===>  10   45   48   50   53   8   44   77   106   108  
Iteration # 9 ===>  8   10   44   45   48   50   53   77   106   108  
 
Here is an array after Merge Sort :    8    10    44    45    48    50    53    77    106    108   

Essayez de déboguer soigneusement le programme pour comprendre les deux méthodes crunchifyMergeSort et crunchifyMerge . Faites-moi savoir si vous avez des questions ou si vous rencontrez des problèmes pour exécuter le code ci-dessus.

Notation Big O / Qu'est-ce qu'une complexité d'algorithme de tri par fusion ?

  • n*log(n)

Fusionner Trier Meilleur Scénario Complexité ?

  • O(n) en cas d'entrée déjà triée