1707004544 李浩

[wmpscc]

java培训（一）

快速和插入排序算法以前没学过，参考百度的

• Test.java

public class Test {
    public static void main(String[] args) {
        //自己用键盘输入int a[10]
        int []a = new int[10];
        Scanner in = new Scanner(System.in);

        for (int i = 0; i < 10; i++)
            a[i] = in.nextInt();
        Factory factory = new Factory();
// 选择排序
        BaseSort select_sort = new SelectSort();
        factory.setSort(select_sort);
        factory.dosort(a);
// 插入排序
        BaseSort insert_sort = new InsertSort();
        factory.setSort(insert_sort);
        factory.dosort(a);
// 快速排序
        BaseSort quick_sort = new QuickSort();
        factory.setSort(quick_sort);
        factory.dosort(a,0,a.length-1);
    }
}

• Factory.java

public class Factory {
    private BaseSort sort;
    //依赖注入
    public void setSort(BaseSort sort){
        this.sort = sort;
    }
    public void dosort(int[] a){
        sort.sort(a);
    }
    public void dosort(int[] a,int low,int high) {
        sort.sort(a,low,high);
        sort.print();
    }
}

• BaseSort.java

public class BaseSort {
    public void sort(int []a){
        System.out.println("排序算法");
    }
    public void sort(int[] a,int low,int high){
    }
    public void print(){
    }
}

• SelectSort.java

public class SelectSort extends BaseSort {
    @Override
    public void sort(int[] a) {
        super.sort(a);
        int minid,i,j,temp;
        for(i = 0; i < a.length; i++){
            minid = i;
            for(j =  i + 1; j < a.length; j++) {
                if(a[minid] > a[j]){
                    minid = j;
                }
            }
            temp = a[minid];
            a[minid] = a[i];
            a[i] = temp;
        }
        for (int t:a) {
            System.out.println(t);
        }
    }
}

• InsertSort.java

public class InsertSort extends BaseSort {
    @Override
    public void sort(int[] a) {
        super.sort(a);
        for(int i = 1; i < a.length; i++){
            for(int j = i; j > 0; j--){
                if(a[j] < a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }else{
                    break;
                }
            }
        }
        for (int t:a ) {
            System.out.println(t);
        }
    }
}

• QuickSort.java

public class QuickSort extends BaseSort {
    int[] result = new int[10];
    @Override
    public void sort(int[] a,int low,int high) {
        super.sort(a);
        int start = low;
        int end = high;
        int key = a[low];
        while(end>start){
            //从后往前比较
            while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后比较
            while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        //递归
        if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
        if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
        result = a;
    }
    @Override
    public void print(){
        for (int t:result) {
            System.out.println(t);
        }
    }
}