/*
* tpop(2): Algorithms and Data Structures
* created on Mar 11, 2011
*/
import java.util.Random;
import java.lang.Math;
/* Quicksort: Java version of quick sort */
public class Quicksort
{
/* Quicksort.sort: quicksort v[left]..v[right] */
static void sort(Object[] v, int left, int right, Cmp cmp){
int i, last;
if (left >= right) //nothing to do
return;
swap(v, left, rand(left, right));//move pivot elem
last = left;
for (i = left+1; i <= right; i++) //artition
if (cmp.cmp(v[i], v[left]) < 0)
swap (v, ++last, i);
swap(v, left, last); //restore pivot elem
sort (v, left, last-1, cmp); //recursively sort
sort (v, last+1, right, cmp); //each part
}
/* Quicksort.swap: swap v[i] and v[j] */
static void swap(Object[] v, int i, int j)
{
Object temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
static Random rgen = new Random();
/* Quicksort.rand: return random integer in [left, right] */
static int rand(int left, int right)
{
return left + Math.abs(rgen.nextInt())%(right-left+1);
}
public static void main(String[] argv)
{
String[] sarr = new String[] {"mark", "tau", "atau", "haitao"};
Quicksort.sort(sarr, 0, sarr.length-1, new Scmp());
System.out.println("The sorted array is " );
for (String s : sarr)
System.out.println(s);
System.out.println("\n");
}
}///:~
阅读(424) | 评论(0) | 转发(0) |
