快速排序：
public class Quick { public static void sort(Comparable[] a,int lo,int hi){ if(hi<=lo)return; int j=partition(a,lo,hi);//切分数组 sort(a,lo,j-1);//左侧递归排序 sort(a,j+1,hi);//右侧递归排序 } //切分 private static int partition(Comparable[] a,int lo,int hi){ int i=lo,j=hi+1; Comparable v=a[lo]; while (true){ while (less(a[++i],v)) if (i==hi) break;//左侧扫描，直到a[i]大于v while (less(v,a[--j])) if (j==lo) break;//右侧扫描，直到a[j]小于v if (i>=j) break; exch(a,i,j);//将a[i],a[j]交换顺序 } exch(a,lo,j); return j; } private static boolean less(Comparable v,Comparable w){ return v.compareTo(w)<0; } private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } private static boolean isSorted(Comparable[] a){ for(int i=1;i<a.length;i++) if(less(a[i],a[i-1])) return false; return true; } private static void show(Comparable[] a){ for (int i=0;i<a.length;i++) System.out.println(a[i]+" "); } public static void main(String[] args){ String[] a={"fgh","asd","wer","asf"}; sort(a,0,a.length-1); show(a); } }三向切分的快速排序
public class Quick3way { /* 指针lt使得a[lo...lt-1]中的元素都小于v， 指针gt使得a[gt+1...hi]中的元素都大于v， 指针i使得a[lt...i]中的元素都等于v， a[i...gt]中的元素都未确定。 1)a[i]小于v，将a[lt]和a[i]交换，lt和i加一； 2)a[i]大于v，将a[gt]和a[i]交换，gt减一； 3)a[i]等于v，将i加一。 */ public static void sort(Comparable[] a,int lo,int hi){ if(lo>=hi)return; int lt=lo,i=lo+1,gt=hi; Comparable v=a[lo]; while (i<=gt){ int temp=a[i].compareTo(v); if (temp<0) exch(a,lt++,i++); else if (temp>0) exch(a,i,gt--); else i++; } sort(a,lo,lt-1); sort(a,gt+1,hi); } private static void exch(Comparable[] a,int i,int j){ Comparable t; t=a[i]; a[i]=a[j]; a[j]=t; } private static void show(Comparable[] a){ for (int i=0;i<a.length;i++) System.out.println(a[i]); } public static void main(String[] args){ String[] a={"fgh","asd","wer","asf"}; sort(a,0,a.length-1); show(a); } }