策略模式实现对数据的排序.doc

策略模式实现对数据的排序一、 策略的抽象类public interface Sort public abstract int sort(int a);二、 具体策略1.希尔排序public class ShellSort implements Sort/ 希尔排序希尔排序希尔排序希尔排序的一种实现方法 public int sort(int a) int temp;for (int k = a.length / 2; k 0; k /= 2) for (int i = k; i = k; j -= k) if (aj - k aj) temp = aj - k;aj - k = aj;aj = temp;return 0; 2. 冒泡排序public class BubbleSort implements Sort/冒泡排序/假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，/如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个，/这样依次类推，直至所有数据都“冒泡”到数据顶上Overridepublic int sort(int a) for(int i=0 ; ia.length ; i+)for(int j=0 ; jaj+1) /用前一个和后一个作比较若前一个大则交换int temp=aj+1; aj+1=aj;aj=temp;return 0;/算法的不变性：许多算法中，有些条件在算法执行过程中始终是不变的。/这些条件被称 为算法的不变性，如果不变性不为真了，则标记出错了；/冒泡排序的效率O（N*N），比较N*N/2，交换N*N/4；3.快速排序public class QuicklySort implements Sort/快速排序/ 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，/则分别对这两部分继续进行排序，直到整个序列有序。Overridepublic int sort(int a) QuicklySort s=new QuicklySort();s.sort(a, 0, a.length-1); /调用含有三个参数的Sort方法return 0; public int sort(int a, int front , int rear) if(frontrear) int p=front; /第一个数 int q=rear; /最后一个数 int temp=aq; /用temp最后一个数作对比 while(pq) while(pq&ap=temp) p+; /记录比temp小的数的个数 aq=ap; /用于后面的递归 while(p=temp) q-; /记录比temp大的数的个数 ap=aq; int mid=q; aq=temp; sort(a,front,mid-1); /对小于aq的数进行递归调用 sort(a,mid+1,rear); return rear; 4.选择排序public class ChoseSort implements Sort/选择排序/假设有N条数据，则暂且标记第0个数据为MIN（最小），使用OUT标记最左边未排序的数据，/然后使用IN标记第1个数据，依次与MIN进行比较，如果比MIN小，则将该数据标记为MIN，/当第一轮比较完后，最终的MIN与OUT标记数据交换，依次类推；Overridepublic int sort(int a) for(int i=0 ; ia.length ; i+)for(int j=1 ; jaj) /用第i个数分别和后面的数作比较int temp=aj; /数据的交换aj=ai;ai=temp;return 0;/选择排序的效率：O（N*N），比较N*N/2，交换N； 选择排序与冒泡排序比较/，比较次数没有明显改变，但交换次数明显减少了很多；5.插入排序public class InsertSort implements Sort/插入排序/插入排序是在部分数据有序的情况下，使用OUT标记第一个无序的数据，/将其提取保存到一个中间变量temp中去，使用IN标记空位置，依次比较temp中的值与IN-1的值，/如果IN-值大于temp的值，则后移，直到遇到第一个比temp小的值，在其下一个位置插入；public int sort(int a) for(int i=1 ; i0&at-1=temp)at=at-1;-t;at=temp;return 0;/插入排序的效率：O（N*N）, 比较N*N/4，复制N*N/4；插入排序在随机数的情况下，/比冒泡快一倍，比选择稍快；在基本有序的数组中，插入排序几乎只需要O（N）；/在逆序情况下，并不比冒泡快；三、 上下文/ 创建一个上下文的类，用于连接Application和具体策略public class Content Sort so;public void setSo(Sort so) /设置具体的某一个策略this.so = so;public int getSort(int a)if(so!=null)return so.sort(a); /调用具体策略的方法，进行排序elsereturn 0;四、 Application类import java.util.Scanner;public class Application public static void main(String args)Application aa=new Application();System.out.println(请输入数组的大小);Scanner in = new Scanner(System.in);int b = in.nextInt();System.out.println(请输入：+b+个数，并换行！);int a = new intb;for(int i=0 ; ia.length ; i+)ai=in.nextInt();Content con = new Content();System.out.println(用快速排序的算法的结果是：);con.setSo(new QuicklySort();con.getSort(a);for(int i=0;ia.length;i+)System.out.print(ai+ );System.out.println();System.out.println(用插入排序的算法的结果是：); con.setSo(new InsertSort(); con.getSort(a);for(int i=0;ia.length;i+)System.out.print(ai+ );System.out.println();System.out.println(用冒泡排序的算法的结果是：); con.setSo(new BubbleSort(); con.getSort(a);for(int i=0;ia.length;i+)System.out.print(ai+ );System.out.println();System.out.println(用选择排序的算法的结果是：); con.setSo(new ChoseSort(); con.getSort(a);for(int i=0;ia.length;i+)System.