脚本宝典收集整理的这篇文章主要介绍了算法基础三:分治算法---归并排序算法,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
import java.util.COMparator;
import java.util.List;
public class Sort {
public static void mergeSort(List<Comparable> a, int p, int r, Comparator comp){
if (p<r){//递归结束的判断条件
int q = (p+r)/2;
mergeSort(a,p,q,comp);
mergeSort(a,q+1,r,comp);
LinearList.merge(a,p,q,r,comp);
}
}
}
import java.util.Comparator;
import java.util.List;
public class LinearList {
public static void merge(List<Comparable> a, int p, int q, int r, Comparator comp){
int i,j,k;
int n1 = q-p+1;
int n2 = r-q;
Comparable[] L = new Comparable[n1];
Comparable[] R = new Comparable[n2];
for (i=0;i<n1;i++)
L[i] = a.get(p+i);
for (j=0;j<n2;j++)
R[j] = a.get(q+1+j);
i=j=0;
k=p;
while (i<n1 && j<n2){
if (comp.compare(L[i],R[j])<0)
a.set(k++,L[i++]);
else
a.set(k++,R[j++]);
}
if (i<n1)
for (;i<n1;i++)
a.set(k++,L[i]);
if (j<n2)
for (;j<n2;j++)
a.set(k++,R[j]);
}
}
Greater
import java.util.Comparator;
public class Greater implements Comparator<Comparable> {
public int compare(Comparable x, Comparable y){
return x.compareTo(y);
}
}
Less
import java.util.Comparator;
public class Less implements Comparator<Comparable> {
@override
public int compare(Comparable o1, Comparable o2) {
return o2.compareTo(o1);
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
public class test {
public static void main(String[] args) {
Integer a[] = {5,1,9,4,6,2,0,3,8,7},i;
String b[] = {"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
Double c[] = {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};
ArrayList<Integer> A = new ArrayList<>();
Vector<String> B = new Vector<>();
LinkedList<Double> C = new LinkedList<>();
for (Integer integer : a) {
A.add(integer);
}
for (String s : b) {
B.add(s);
}
for (Double aDouble : c) {;
C.add(aDouble);
}
Sort.mergeSort((List) A,0,9,new Greater());
Sort.mergeSort((List) B,0,5,new Less());
Sort.mergeSort((List) C,0,9,new Greater());
System.out.PRintln(A);
System.out.println(B);
System.out.println(C);
}
}
以上是脚本宝典为你收集整理的算法基础三:分治算法---归并排序算法全部内容,希望文章能够帮你解决算法基础三:分治算法---归并排序算法所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。