排序算法之归并
2021-02-08 18:19
标签:数组 边界条件 i++ 算法 com lse private 归并排序 初始 归并算法是在分治的思想下,将数组递归的分为两半,分别排序后,再归并成 优点:对于长度为 N 的数组,无论规模多大,排序所需时间总和 NlogN 成正比。 注意:归并排序的核心不是交换数据。 自顶向下的归并算法过程是将数组递归到底层,进行两两比较,再向上合并。 排序算法之归并 标签:数组 边界条件 i++ 算法 com lse private 归并排序 初始 原文地址:https://www.cnblogs.com/juzhuxiaozhu/p/12770834.html归并排序
整个数组。所谓分治,即分而治之。
缺点:排序所需额外空间和 N 成正比。1. 自顶向下的归并排序
package mysort;
//归并类
class Merge {
//定义一个临时辅助数组
private static Comparable[] aux;
//对外提供排序方法
public static void sort(Comparable[] a){
//初始化辅助数组(注意不要减1)
aux=new Comparable[a.length];
sort(a,0,a.length-1);
}
//内部真正起到排序作用的方法
private static void sort(Comparable[] a,int lo,int hi){
//边界条件
if(himid) {
a[k]=aux[j++];
}
//右边输出完了,开始只取左边元素
else if(j>hi){
a[k]=aux[i++];
}
//比较两边,此为小者在右边的情况
else if (less(aux[j],aux[i])){
a[k]=aux[j++];
}
//相等或较大则取左边
else {
a[k]=aux[i++];
}
}
}
//此方法用于判断前者是否小于后者
private static boolean less(Comparable m, Comparable n){
return m.compareTo(n)
2. 自底向上的归并排序
而自底向上的归并排序则直接将数组元素进行比较,然后两两归并,四四归并,八八归并,直到合成一个数组。private static void sort(Comparable[] a){
//sz为子数组的大小:1、2、4、8、16...
for(int sz=1;sz
3. 两者联系
上一篇:7-37 模拟EXCEL排序 (25分)--优先队列
下一篇:0424数组练习