随笔 - 117  文章 - 72  trackbacks - 0

声明:原创作品(标有[原]字样)转载时请注明出处,谢谢。

常用链接

常用设置
常用软件
常用命令
 

订阅

订阅

留言簿(7)

随笔分类(130)

随笔档案(123)

搜索

  •  

积分与排名

  • 积分 - 152311
  • 排名 - 391

最新评论

[关键字]:java,design pattern,设计模式,《Java与模式》学习,Strategy Pattern,策略模式
[环境]:StarUML5.0 + JDK6
[作者]:Winty (wintys@gmail.com) http://www.blogjava.net/wintys/
[正文]:
策略模式:排序算法

package pattern.strategy.sort;

/**
 * 策略模式:Strategy Pattern
 *
 * 排序算法策略
 *
 * @version 2009-05-22
 * @author Winty (wintys@gmail.com) http://www.blogjava.net/wintys
 *
 */
public class SortStrategyTest {
    public static void main(String[] args) {
        Sorter<?> sorter;
            
        Integer[] data = new Integer[]{548,85,984,3,2,44,99};
        sorter = new Sorter<Integer>(data , "QuickSort");
        sorter.printArray();
        sorter.sort();
        sorter.printArray();
        
        String[] strs = new String[]{"B","C","D","A","X","F","E"};
        sorter = new Sorter<String>(strs , "InsertionSort");
        sorter.printArray();
        sorter.sort();
        sorter.printArray();        
    }
}

class Sorter<T extends Comparable<T>>{
    private T[] data;
    private SortStrategy<T> strategy;
    
    @SuppressWarnings("unchecked")
    public Sorter(T[] data , String sortStrategy){
        this.data = data;
        
        //利用反射动态加载策略类
        String pack = this.getClass().getPackage().getName();
        pack += ".";
        try {

            Class<?> cl = Class.forName(pack + sortStrategy);
            strategy = (SortStrategy<T>) cl.newInstance();//unchecked
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
    }
    
    public void sort(){
        strategy.sort(data);
    }
    
    public void printArray(){
        for(int i=0;i<data.length;i++){
            System.out.print(""+data[i]+" ");
        }
        System.out.println("");
    }
}

/**
 * 抽象排序算法类
 * @author Winty
 *
 * @param <T> 实现了Comparable<T>接口的类
 */
abstract class SortStrategy<T extends Comparable<T>>{
    public abstract void sort(T[] data);
}

/**
 * 插入排序
 * @author Winty
 */
class InsertionSort<T extends Comparable<T>> extends SortStrategy<T>{

    @Override
    public void sort(T[] data) {
        int len;
        T temp;
        len=data.length;

        for(int i=1;i<len;i++){
            int k;
            k=0;
            temp=data[i];
            for(int j=i-1;j>=0;j--){
                k=i;
                if(data[j].compareTo(temp) > 0){
                    data[j+1]=data[j];
                    k=j;
                }
                else if(data[j].compareTo(temp) < 0){
                    k=j+1;
                    break;
                }
            }
            data[k]=temp;
        }    
    }    
}

/**
 * 快速排序
 * @author Winty
 */
class QuickSort<T extends Comparable<T>> extends SortStrategy<T>{

    @Override
    public void sort(T[] data) {
        quick(data , 0 , data.length - 1);        
    }

    private void quick(T[] data , int p , int r){
        int q;

        if (p < r){
            q = partition(data , p , r);
            quick(data , p , q - 1);
            quick(data , q + 1 , r);
        }
    }

    private int partition(T[] data , int p ,int r){
        int i;
        T pivot , temp;
        
        i = p - 1;
        pivot = data[r];

        for(int j = p; j <= r - 1;j++){
            if(data[j].compareTo(pivot) < 0){
                i++;
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        temp = data[i + 1];
        data[i + 1] = data[r];
        data[r] = temp;

        return i + 1;
    }
}

posted on 2009-06-14 17:54 天堂露珠 阅读(1294) 评论(2)  编辑  收藏 所属分类: Pattern

FeedBack:
# re: [原]策略模式-排序算法 2009-06-14 18:51 爱吃鱼头
很好的例子,UML图画得也很漂亮,收藏了。  回复  更多评论
  
# re: [原]策略模式-排序算法 2009-06-15 13:09 找个美女做老婆
厉害,我用排序的时候,直接用的JAVA的方法。
Java乐园 -Java学习者的天堂。 http://www.javaly.cn Java学习交流网站 Java乐园群号:15651281  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: