对于数组A,起始位置在p,最后一个元素在r。先分成两个序列,然后对左边和右边的序列分别排序,最后合并。
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); } }