0001 /* 0002 * 归并排序算法 0003 * 针对向量和列表两种情况,merge()方法的具体实现不同 0004 * 这里只针对基于列表的序列,给出算法实现 0005 */ 0006 0007 package dsa; 0008 0009 public class Sorter_Mergesort implements Sorter { 0010 protected Comparator C; 0011 0012 public Sorter_Mergesort() 0013 { this(new ComparatorDefault()); } 0014 0015 public Sorter_Mergesort(Comparator comp) 0016 { C = comp; } 0017 0018 public void sort(Sequence S) {//Mergesort 0019 int n = S.getSize(); 0020 if (1 >= n) return; //递归基 0021 Sequence S1 = new Sequence_DLNode(); 0022 Sequence S2 = new Sequence_DLNode(); 0023 while (!S.isEmpty()) {//将S均匀地分成两个子序列S1和S2 0024 S1.insertLast(S.remove(S.first())); 0025 if (!S.isEmpty()) S2.insertLast(S.remove(S.first())); 0026 } 0027 sort(S1); sort(S2); 0028 merge(S, S1, S2); 0029 } 0030 0031 public void merge(Sequence S, Sequence S1, Sequence S2) {//有序列表的归并算法 0032 while (!S1.isEmpty() || !S2.isEmpty()) { 0033 Object e; 0034 //在两个子列表变为空之前,不断地摘出两个首元素中的小者e 0035 if (S1.isEmpty()) 0036 e = S2.remove(S2.first()); 0037 else if (S2.isEmpty()) 0038 e = S1.remove(S1.first()); 0039 else if (0 < C.compare(S1.first().getElem(), S2.first().getElem())) 0040 e = S2.remove(S2.first()); 0041 else 0042 e = S1.remove(S1.first()); 0043 //将该元素插至S的尾部 0044 S.insertLast(e); 0045 }//while 0046 } 0047 }