Chinaunix首页 | 论坛 | 博客
  • 博客访问: 222476
  • 博文数量: 136
  • 博客积分: 2919
  • 博客等级: 少校
  • 技术积分: 1299
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-11 09:08
文章分类

全部博文(136)

文章存档

2013年(1)

2011年(135)

我的朋友

分类: Java

2011-03-11 15:39:20

/*
 * 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");
}
}///:~
阅读(449) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~