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
| package sort;
import java.util.Random;
public class MergeSort {
int data[];
private Random gen = new Random();
public MergeSort() {
data= new int []{3,4,1,2,0};
}
public MergeSort(int length) {
data=new int[length];
for(int i = 0;i<data.length;i++){
data[i]= 1+gen.nextInt(99);
}
}
public void sort(){
sortArray(0,data.length-1);
}
private void sortArray(int low, int high){
if((high - low)>=1){
int m = (low + high)/2;
sortArray(low,m);
sortArray(m+1,high);
merge(low,m,high);
}
}
private void merge(int l,int m, int h ){
int [] temp= new int[data.length];
int left = l;
int right=m+1;
int index =l;
while((left<=m)&&(right <= h) ){
if(data[right]<data[left]){
temp[index++]=data[right++];
}
else{
temp[index++]=data[left++];
}
}
if(left==m+1){
while(right<=h)
temp[index++]=data[right++];
}
else
{
while(left<=m)
temp[index++]=data[left++];
}
for(int i=l;i<=h;i++)
data[i]=temp[i];
}
public void afficher(int l, int h){
for(int k=l;k<h;k++)
System.out.print(data[k]+" ");
System.out.println();
}
public static void main(String[] args) {
int n= 10;
MergeSort ms = new MergeSort(n);
ms.afficher(0,ms.data.length);
ms.sort();
System.out.println("fin tri ...!");
ms.afficher(0,ms.data.length);
}
} |
Tri par fusion (Merge Sort)
Répondre avec citation
Envoyé par saimer
Partager