简单工厂模式和策略模式实现简单排序算法。

第一次使用设计模式编写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 long[arrays.length];
    }
    
    // 具体排序方法。
    public abstract int[] sort(int[] array, int length);
    
    // 显示结果 。
    public void display(String name) {
        System.out.println("排序数量\t\t" + 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(arrays[n]), arrays[n]);
                long end = Calendar.getInstance().getTimeInMillis();
                time += (end - begin);
            }
            sortTimes[n] = time / turns;
        }
        for (int i = 0; i < arrays.length; ++i) {
            System.out.println("" + arrays[i] + "\t\t" + sortTimes[i]);
        }
    }

    // 生成指定长度的数组。
    public int[] getRandArray(int n) {
        int[] array = new int[n];
        Random rand = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = rand.nextInt(range);
        }
        return array;
    }

    // 测试数组是否排序成功，顺序由小到大。
    public boolean isSorted(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    }
    
    //显示数组
    public void display(int[] array){
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
    }
}

=================================工厂类==============================

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 (sortname[0]) {
        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接口。
	@Test
	public void testBubbleSort() {
		sort = SortFactory.creatSort("BubbleSort", arrays, range);
		sort.display("冒泡排序");
	}

	// 选择排序。
	@Test
	public void testSelectSort() {
		sort = SortFactory.creatSort("SelectSort", arrays, range);
		sort.display("选择排序");
	}

	// 归并排序。
	@Test
	public void testMergeSort() {
		sort = SortFactory.creatSort("MergeSort", arrays, range);
		sort.display("归并排序");
	}

	// 堆排序。
	@Test
	public void testHeapSort() {
		sort = SortFactory.creatSort("HeapSort", arrays, range);
		sort.display("堆排序");
	}

	// 插入排序。
	// 使用简单工厂加策略模式实现。用户只需知道SortContext，进一步降低耦合性。
	@Test
	public void testInsertSort() {
		sortContext = new SortContext("InsertSort", arrays, range);
		sortContext.display("插入排序 ");
	}

	// 系统排序，快速排序。
	@Test
	public 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 (sortname[0]) {
		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 stub
	}

	public BubbleSort() {
		// TODO Auto-generated constructor stub
	}

	// 冒泡。
	@Override
	public int[] sort(int[] array, int length) {
		int temp;
		for (int out = 0; out < length; out++)
			for (int in = length - 1; in > out; in--)
				if (array[in] < array[in - 1]) {
					temp = array[in];
					array[in] = array[in - 1];
					array[in - 1] = temp;
				}
		return array;
	}
}

=================================选择排序======================================

package sort;

public class SelectSort extends Sort {

	SelectSort() {

	}

	SelectSort(int[] arrays, int range) {
		super(arrays, range);
	}

	// 选择排序，从小到大。
	@Override
	public int[] sort(int[] array, int length) {
		// TODO Auto-generated method stub
		int left, right, min, temp;
		for (left = 0; left < length - 1; left++) {
			min = left;
			for (right = left + 1; right < length; right++) {
				if (array[right] < array[min])
					min = right;
			}
			temp = array[left];
			array[left] = array[min];
			array[min] = temp;
		}
		return array;
	}

}

=====================================插入排序==================================

package sort;

public class InsertSort extends Sort {

	public InsertSort() {
		// TODO Auto-generated constructor stub
	}

	InsertSort(int[] arrays, int range) {
		super(arrays, range);
		// TODO Auto-generated constructor stub
	}

	// 插入。
	@Override
	public int[] sort(int[] array, int length) {
		int left, right, temp;

		for (right = 1; right < length; right++) {
			temp = array[right];
			left = right - 1;
			while (left >= 0 && (temp < array[left])) {
				array[left + 1] = array[left];
				left--;
			}
			array[left + 1] = temp;
		}
		return array;
	}
}

=================================归并排序======================================

package sort;

import java.util.Arrays;

public class MergeSort extends Sort {

	public MergeSort() {
		// TODO Auto-generated constructor stub
	}

	MergeSort(int[] arrays, int range) {
		super(arrays, range);
		// TODO Auto-generated constructor stub
	}

	@Override
	public int[] sort(int[] array, int length) {
		// TODO Auto-generated method stub
		if (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 (a[i] <= b[j]) {
				ary[k++] = a[i++];
			} else {
				ary[k++] = b[j++];
			}
		}

		for (; i < a.length; ++i) {
			ary[k++] = a[i];
		}
		for (; j < b.length; ++j) {
			ary[k++] = b[j];
		}
	}

}

======================================堆排序===================================

package sort;

public class HeapSort extends Sort {

	HeapSort() {

	}

	HeapSort(int[] arrays, int range) {
		super(arrays, range);
		// TODO Auto-generated constructor stub
	}

	@Override
	public int[] sort(int[] array, int length) {
		// TODO Auto-generated method stub
		buildHeap(array); // 首先，建一个堆， 此时a[0] 就是最大的元素
		for (int i = length - 1; i > 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 < n && a[left] > a[i]) {
			return false;
		}

		if (right < n && a[right] > a[i]) {
			return false;
		}

		return isHeap(a, left) && isHeap(a, right); // 左右子树也是大顶堆。
	}

	// 不断调整，直到整个数组变成堆。
	// i的左右子树都是堆 (j后面的元素不管，不属于堆), 我们要把他调整成堆。
	void heapify(int[] a, int i, int j) {
		int left = i * 2 + 1;
		int right = i * 2 + 2;
		if (left > j) { // 没有左子树
			return;
		}

		int large = left;
		if (right <= j && a[left] < a[right]) {
			large = right;
		}

		if (a[i] < a[large]) { // 如果根元素比 large小，重新调整。
			swap(a, i, large);
			heapify(a, large, j); // 继续操作large子树。
		}
	}

	private void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

===================================系统排序====================================

package sort;

import java.util.Arrays;

public class SystemSort extends Sort {

	public SystemSort() {
		// TODO Auto-generated constructor stub
	}

	SystemSort(int[] arrays, int range) {
		super(arrays, range);
		// TODO Auto-generated constructor stub
	}

	@Override
	public int[] sort(int[] array, int length) {
		// TODO Auto-generated method stub
		Arrays.sort(array);
		return array;
	}

}