简单工厂模式和策略模式实现一些排序算法.docx

第一次使用设计模式编写java版的排序算法。欢迎指点，有不足之处还望不吝赐教。本人略懒，UML图就不画了。=Sort类，所有将要实现的算法的母类=package sort;import java.util.Calendar;import java.util.Random;public abstract class Sort / 存储排序数量的数组。 int arrays; / 指定随机生成的数字的范围。 int range; / 存储对应排序数量所用的时间。 long sortTimes; Sort() Sort(int arrays, int range) this.arrays = arrays; this.range = range; this.sortTimes = new longarrays.length; / 具体排序方法。 public abstract int sort(int array, int length); / 显示结果 。 public void display(String name) System.out.println(排序数量tt + name + (ms); for (int n = 0; n arrays.length; n+) int turns = 10; / 排十次，求平均。 long time = 0; for (int j = 0; j turns; +j) long begin = Calendar.getInstance().getTimeInMillis(); this.sort(this.getRandArray(arraysn), arraysn); long end = Calendar.getInstance().getTimeInMillis(); time += (end - begin); sortTimesn = time / turns; for (int i = 0; i arrays.length; +i) System.out.println( + arraysi + tt + sortTimesi); / 生成指定长度的数组。 public int getRandArray(int n) int array = new intn; Random rand = new Random(); for (int i = 0; i array.length; i+) arrayi = rand.nextInt(range); return array; / 测试数组是否排序成功，顺序由小到大。 public boolean isSorted(int array) for (int i = 0; i arrayi + 1) return false; return true; /显示数组 public void display(int array) for(int i = 0; i array.length; i+) System.out.print(arrayi + ); =工厂类=package sort;public class SortFactory public static Sort creatSort(String sortName, int arrays, int range) Sort sort = null; char sortname = sortName.toCharArray(); / jdk 1.7过后switch就支持String类型了。 switch (sortname0) case B: / 冒泡排序 sort = new BubbleSort(arrays, range); break; case S: / 选择排序 sort = new SelectSort(arrays, range); break; case I: / 插入排序 sort = new InsertSort(arrays, range); break; case M: / 归并排序 sort = new MergeSort(arrays, range); break;/ case S: / 系统排序/ sort = new SystemSort(arrays, range);/ break; case H: / 堆排序 sort = new HeapSort(arrays, range); break; return sort; =测试类=/ 其中插入排序和系统排序是策略模式实现。package sort;import org.junit.Test;public class SortTest / 存储排序数量的数组。int arrays = 1000, 2000, 5000, 10000, 20000, 50000, 100000 ;/ 指定随机生成的数字的范围(0-1000)。int range = 1000;/ 使用简单工厂创建具体排序类。Sort sort = null;/ 使用策略模式实现，适用于调用的方法都是做的相同的工作，只是实现不同。SortContext sortContext;/ 冒泡排序，使用简单工厂实现。用户需要知道工厂类和Sort接口。Testpublic void testBubbleSort() sort = SortFactory.creatSort(BubbleSort, arrays, range);sort.display(冒泡排序);/ 选择排序。Testpublic void testSelectSort() sort = SortFactory.creatSort(SelectSort, arrays, range);sort.display(选择排序);/ 归并排序。Testpublic void testMergeSort() sort = SortFactory.creatSort(MergeSort, arrays, range);sort.display(归并排序);/ 堆排序。Testpublic void testHeapSort() sort = SortFactory.creatSort(HeapSort, arrays, range);sort.display(堆排序);/ 插入排序。/ 使用简单工厂加策略模式实现。用户只需知道SortContext，进一步降低耦合性。Testpublic void testInsertSort() sortContext = new SortContext(InsertSort, arrays, range);sortContext.display(插入排序 );/ 系统排序，快速排序。Testpublic void testSystemSort() sortContext = new SortContext(SystemSort, arrays, range);sortContext.display(系统排序);=策略模式=package sort;public class SortContext Sort sort = null;/ 简单工厂实现具体策略。public SortContext(String sortName, int arrays, int range) char sortname = sortName.toCharArray();/ jdk 1.7过后switch就支持String类型了。switch (sortname0) case B: / 冒泡排序sort = new BubbleSort(arrays, range);break;case I: / 插入排序sort = new InsertSort(arrays, range);break;case M: / 归并排序sort = new MergeSort(arrays, range);break;case S: / 系统排序sort = new SystemSort(arrays, range);break;case H: / 堆排序sort = new HeapSort(arrays, range);break;/ 策略模式，封装公共的功能。public void display(String name) sort.display(name);=冒泡排序=package sort;public class BubbleSort extends Sort BubbleSort(int arrays, int range) super(arrays, range);/ TODO Auto-generated constructor stubpublic BubbleSort() / TODO Auto-generated constructor stub/ 冒泡。Overridepublic int sort(int array, int length) int temp;for (int out = 0; out out; in-)if (arrayin arrayin - 1) temp = arrayin;arrayin = arrayin - 1;arrayin - 1 = temp;return array;=选择排序=package sort;public class SelectSort extends Sort SelectSort() SelectSort(int arrays, int range) super(arrays, range);/ 选择排序，从小到大。Overridepublic int sort(int array, int length) / TODO Auto-generated method stubint left, right, min, temp;for (left = 0; left length - 1; left+) min = left;for (right = left + 1; right length; right+) if (arrayright arraymin)min = right;temp = arrayleft;arrayleft = arraymin;arraymin = temp;return array;=插入排序=package sort;public class InsertSort extends Sort public InsertSort() / TODO Auto-generated constructor stubInsertSort(int arrays, int range) super(arrays, range);/ TODO Auto-generated constructor stub/ 插入。Overridepublic int sort(int array, int length) int left, right, temp;for (right = 1; right = 0 & (temp arrayleft) arrayleft + 1 = arrayleft;left-;arrayleft + 1 = temp;return array;=归并排序=package sort;import java.util.Arrays;public class MergeSort extends Sort public MergeSort() / TODO Auto-generated constructor stubMergeSort(int arrays, int range) super(arrays, range);/ TODO Auto-generated constructor stubOverridepublic int sort(int array, int length) / TODO Auto-generated method stubif (length = 0 | length = 1) return null;int mid = length / 2;int a = Arrays.copyOfRange(array, 0, mid);int b = Arrays.copyOfRange(array, mid, array.length);sort(a, a.length);sort(b, b.length);merge(a, b, array);return array;private void merge(int a, int b, int ary) int i = 0;int j = 0;int k = 0;while (i a.length & j b.length) if (ai = bj) aryk+ = ai+; else aryk+ = bj+;for (; i a.length; +i) aryk+ = ai;for (; j 0; i-) / 选出最大的元素swap(array, 0, i); / 在这之后， i 以及后面的元素都是有序的heapify(array, 0, i - 1); / 根元素由于被交换过，所以需要进行一次调整,让他再变成堆。return array;void buildHeap(int array) int n = array.length;for (int i = n / 2 - 1; i = 0; -i) / n / 2 - 1, 就是最后一个有子节点的元素heapify(array, i, n - 1);/ 判断是否为大顶堆。boolean isHeap(int a, int i) int n = a.length;if (i = n) return true;int left = 2 * i + 1; / 左节点int right = 2 * i + 2; / 右节点if (left ai) return false;if (right ai) return false;return isHeap(a, left) & isHeap(a, right); / 左右子树也是大顶堆。/ 不断调整，直到整个数组变成堆。/ i的左右子树都是堆 (j后面的元素不管，不属于堆), 我们要把