- it技术
- 归并排序
目录
要求代码复杂度时间复杂度空间复杂度
稳定性
要求
将数值数组按从小到大排序。
代码
public class Merge {
private static Comparable
[] assist
;
public static void sort(Comparable
[] a
) {
assist
= new Comparable[a
.length
];
int lo
= 0;
int hi
= a
.length
-1;
sort(a
,lo
,hi
);
}
private static void sort(Comparable
[] a
,int lo
, int hi
) {
if (lo
>=hi
) {
return;
}
int mid
= (lo
+hi
)/2;
sort(a
,lo
,mid
);
sort(a
,mid
+1,hi
);
merge(a
,lo
,mid
,hi
);
}
private static void merge(Comparable
[] a
, int lo
, int mid
, int hi
) {
int i
= lo
;
int p1
= lo
;
int p2
= mid
+1;
while(p1
<=mid
&& p2
<=hi
) {
if (less(a
[p1
],a
[p2
])) {
assist
[i
++] = a
[p1
++];
} else {
assist
[i
++] = a
[p2
++];
}
}
while (p1
<=mid
) {
assist
[i
++] = a
[p1
++];
}
while (p2
<=hi
) {
assist
[i
++] = a
[p2
++];
}
for (int index
=lo
;index
<=hi
;index
++) {
a
[index
] = assist
[index
];
}
}
private static boolean less(Comparable v
, Comparable w
) {
return v
.compareTo(w
) <= 0;
}
}
}
import java
.util
.Arrays
;
public class Test {
public static void main(String
[] args
) throws Exception
{
Integer
[] arr
= {8,6,1,2,7,40,8,56,21,88};
Merge
.sort(arr
);
System
.out
.println(Arrays
.toString(arr
));
}
}
[1, 2, 6, 7, 8, 8, 21, 40, 56, 88]
复杂度
时间复杂度
O(nlogn)
空间复杂度
O(n)
稳定性
稳定
