1607094147孟庆辉

[MengQingH]

package 基本程序;

import java.util.Arrays;

public class 作业1 {
    public static void main(String[] args) {
        int[] a = {8, 6, 1, 5, 95, 32};
        int[] b = Arrays.copyOf(a, a.length), c = Arrays.copyOf(a, a.length);
        Factory factory = new Factory();
        BaseSort select_sort = new SelectSort();
        BaseSort insert_sort = new InsertSort();
        BaseSort quick_sort = new QuickSort();
        //选择排序
        factory.setSort(select_sort);
        factory.doSort(a);
        select_sort.display(a);
        //快速排序
        factory.setSort(quick_sort);
        factory.doSort(b);
        quick_sort.display(b);
        //插入排序
        factory.setSort(insert_sort);
        factory.doSort(c);
        insert_sort.display(c);
    }
}

class Factory{
    private BaseSort sort;
    public void setSort(BaseSort sort){
        this.sort = sort;
    }
    public void doSort(int[] a) {
        sort.sort(a);
    }
}
class BaseSort{
    public void sort(int[] a){
        System.out.println("排序算法");
    }
    public void display(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

class SelectSort extends BaseSort {
    public void sort(int[] a) {
        int temp;
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] < a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
    }
}
class InsertSort extends BaseSort{
    public void sort(int[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i-1; j >= 0 ; j--) {
                int temp;
                if(a[j] < a[j+1]) {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
                else break;
            }
        }
    }
}
class QuickSort extends BaseSort{
    public void sort(int[] a){
        int left = 0;
        int right = a.length - 1;
        sort1(a,left,right);
    }
    public void sort1(int[] a,int left,int right){
        int i,j,temp;
        i = left;j = right;
        temp = a[left];
        while (i < j){
            while (i < j && a[j] >= temp)
                j--;
            if(i < j){
                a[i] = a[j];
            }
            while (i < j && a[i] <= temp)
                i++;
            if(i < j) {
                a[j] = a[i];
            }
        }
        a[i] = temp;
        if(left < i-1)
            sort1(a,left,i-1);
        if(i+1 < right)
            sort1(a,i+1,right);
    }

}