Complexity : 1.39 W N lg R.
Not a stable sort.
Source:
Output:
are
by
sea
seashells
seashells
sells
sells
she
she
shells
surely
the
the
Not a stable sort.
Source:
public class ThreeWSQS { public static int charAt(String s, int i){ if(i<s.length()-1)return s.charAt(i); else return -1; } public static void sort(String[] s){ sort(s, 0, s.length-1, 0); } private static void exch(String[] s, int a, int b){ String ss = s[a]; s[a] = s[b]; s[b] = ss; } private static void sort(String[] s, int lo, int hi, int d){ if(hi<=lo)return; int lt = lo, gt = hi; int i = lo+1; int c = charAt(s[lo], d); while(i<=gt){ int cc = charAt(s[i], d); if(cc<c)exch(s, lt++, i++); else if(cc>c)exch(s, i, gt--); else i++; } sort(s, lo, lt-1, d); if(c>=0)sort(s, lt, gt, d+1); sort(s, gt+1, hi, d); } public static void main(String[] args){ String[] s = new String[]{"she", "sells", "seashells", "by", "the", "sea", "the", "shells", "she", "sells", "are", "surely", "seashells"}; sort(s); for(String ss:s)System.out.println(ss); } }
Output:
are
by
sea
seashells
seashells
sells
sells
she
she
shells
surely
the
the
No comments:
Post a Comment