1607064140-王仁洪

[sunnyandgood]

import java.util.Scanner;

//父类
class ParentSort
{
	public void sort(int[] array)
	{
		System.out.println("排序算法");
	}
	public void showArray(int[] array)
	{
		for(int i:array)
		{
			System.out.print(i+" ");
		}
	}
}

//选择排序类
class SelectSort extends ParentSort
{
	@Override
	public void sort(int[] array)
	{
		int index;
		for(int i=1;i<array.length;i++)
		{
			index = 0;
			for(int j=1;j<=array.length-i;j++)
			{
				if(array[j]>array[index])
				{
					index=j;
				}
			}
			int temp = array[array.length-i];
			array[array.length-i] = array[index];
			array[index] = temp;
		}
		System.out.print("选择排序：");
		showArray(array);
	}
}

//插入排序类
class InsertSort extends ParentSort
{
	@Override
	public void sort(int[] array)
	{
		for(int i=0;i<array.length;i++) 
		{
			 int j = i - 1;
			 int temp = array[i];   //记录要插入的数据  
			 while(j>=0 && array[j]>temp)  //从后向前，找到比其小的数的位置 
			 {
				 array[j+1] = array[j]; //向后挪动  
				 j--;
			 }
			 if(j != i-1) //存在比其小的数 
			 {
				 array[j+1] = temp;
			 }
		}
		System.out.print("插入排序：");
		showArray(array);
	}
}

//快速排序类
class FastSort extends ParentSort
{
	@Override
	public void sort(int[] array)
	{
		int left = 0;
		int right = array.length-1;
		sort(array,left,right);
		System.out.print("快速排序：");
		showArray(array);
	}
	
	public void sort(int[] array,int left1,int right1)
	{
		int left = left1;
        int right = right1;
        int temp = 0;
        if(left <= right) //待排序的元素至少有两个的情况
        {  
            temp = array[left];  //待排序的第一个元素作为基准元素
            while(left != right)//从左右两边交替扫描，直到left = right
            {   
                while(right > left && array[right] >= temp)  
                     right --;        //从右往左扫描，找到第一个比基准元素小的元素
                  array[left] = array[right];  //找到这种元素array[right]后与array[left]交换

                while(left < right && array[left] <= temp)
                     left ++;         //从左往右扫描，找到第一个比基准元素大的元素
                  array[right] = array[left];  //找到这种元素array[left]后，与array[right]交换

            }
            array[right] = temp;    //基准元素归位
            
            sort(array,left1,left-1);  //对基准元素左边的元素进行递归排序
            sort(array,left+1,right1);  //对基准元素右边的进行递归排序
        }
	}
}

//策略类
class Factory
{
	private ParentSort sort;
	//依赖注入 
	public void setSort(ParentSort sort)
	{
		this.sort = sort;
	}
	public void doSort(int[] array)
	{
		sort.sort(array);
	}
}

//测试类
public class SortTest
{
	public static void main(String[] args) 
	{
		int[] array = {63,4,24,1,3,15};
		Factory factory = new Factory();
		
		System.out.println("1、选择排序");
		System.out.println("2、插入排序");
		System.out.println("3、快速排序");
		
		System.out.print("请选择：");
		Scanner input = new Scanner(System.in);
		int number = input.nextInt();
		
		if(number == 1)
		{
			ParentSort selectSort = new SelectSort();
			factory.setSort(selectSort);
			factory.doSort(array);
		}
		
		if(number == 2)
		{
			ParentSort insertSort = new InsertSort();
			factory.setSort(insertSort);
			factory.doSort(array);
		}
		
		if(number == 3)
		{
			ParentSort fastSort = new FastSort();
			factory.setSort(fastSort);
			factory.doSort(array);
		}
	}
}