0001 /* 0002 * 快速排序算法 0003 * 针对向量和列表两种情况,createPivot()方法的具体实现不同 0004 * 这里只针对基于向量的序列,给出算法实现 0005 */ 0006 0007 package dsa; 0008 0009 public class Sorter_Quicksort implements Sorter { 0010 private Comparator C; 0011 0012 public Sorter_Quicksort() 0013 { this(new ComparatorDefault()); } 0014 0015 public Sorter_Quicksort(Comparator comp) 0016 { C = comp; } 0017 0018 public void sort(Sequence s)//入口方法 0019 { qsort(s, 0, s.getSize() - 1); } 0020 0021 public void qsort(Sequence S, int lo, int hi) {//Quicksort 0022 if (lo >= hi) return; 0023 int mi = createPivot(S, lo, hi); 0024 qsort(S, lo, mi - 1); 0025 qsort(S, mi + 1, hi); 0026 } 0027 0028 public int createPivot(Sequence S, int lo, int hi) {//确定轴点 0029 while (lo < hi) { 0030 while ((lo < hi) && (C.compare(S.getAtRank(lo), S.getAtRank(hi)) <= 0)) hi--; 0031 swap(S, lo, hi); 0032 while ((lo < hi) && (C.compare(S.getAtRank(lo), S.getAtRank(hi)) <= 0)) lo++; 0033 swap(S, lo, hi); 0034 } 0035 return lo; 0036 } 0037 0038 private void swap(Sequence S, int i, int j) {//交换S[i]和S[j] 0039 Object temp = S.getAtRank(i); 0040 S.replaceAtRank(i, S.getAtRank(j)); 0041 S.replaceAtRank(j, temp); 0042 } 0043 }