看过设计模式后写排序算法

以前写过插入排序算法http://blog.csdn.net/xiaoxiaobian3310903/article/details/8616126,后来发现在写冒泡拍戏,希尔排序,归并排序的时候测试代码还需要写一遍,以前看过一点设计模式,只是看看那个模式是干嘛的,真正的没有看过设计模式的书,为了找工作好好的看了下设计模式,突然发现设计模式只是在做项目时如何进行类的设计以及代码设计的,有种顿悟的感觉,当然可能理解的还不够，如果有不合适的地方，希望得到您的指点，所以我应用设计模式的思想重新写了下各个排序算法,以下是设计思路.

由于我只对排序算法进行处理，所以每个算法操作的数据对象是一个int型的数组，这个可以放在基类中，由于测试算法正确性是需要不同的数据，所以将数据用另一个类生成，每个算法都需要输出数组的内容，所以提供一个输出方法printArray()，同时每个算法中有个字符串来表示当前算法是哪个算法，子类需要进行设置，所以提供一个公共的 setTag(String pTag)方法，为了测试算法的运行时间需要在算法开始前和算法结束前分别获取当前的系统时间，同时算法结束后需要输出算法执行的时间，所以提供loadBeginTime()、loadEndTime()和printDuration()，由于每个算法都是排序，但排序的方式不同，所以提供一个抽象的ownSort(int[] data)方法供子类实现，提供一个共有的sort()，这个sort中调用ownSort函数进行各种排序，所以每个排序算法只需要实现ownSort中的方法就可以，由于每个算法使用不同的字符串标识，所以在每个排序算法的构造函数中应调用setTag方法进行设置。在测试各个排序算法时，分别创建一个基类的对象指向不同的子类，执行sort方法进行排序。

基类如下：

public abstract class SortBase {
	private int[] data;
	private String tag;
	private long beginTime;
	private long endTime;
	public SortBase(){
		data = DataSource.getIntArray();
	}
	
	public void setTag(String pTag){
		tag = pTag;
	}
	public abstract void ownSort(int[] data);
	
	public void printArray(){
		for(int i = 0; i < data.length; i++){
			DataSource.logs(tag + " i = " + i  + " value = " + data[i]);
		}
	}	
	
	public void loadBeginTime(){
		beginTime = System.currentTimeMillis();
		endTime = beginTime;
	}
	
	public void loadEndTime(){
		endTime = System.currentTimeMillis();
	}
	
	public void printDuration(){
		DataSource.logs(tag + " duration = " + (endTime - beginTime));
	}
	
	public void sort(){
		ownSort(data);
	}
}

冒泡排序：

public class SortByBubble extends SortBase{
	
	public SortByBubble(){
		this.setTag("Bubble");
	}

	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		int tmp = 0;
		for(int i = 1; i <= data.length - 1; i++){
			for(int j = 0; j <= data.length - 1 - i; j++){
				if(data[j] > data[j + 1]){
					tmp = data[j];
					data[j] = data[j + 1];
					data[j + 1] = tmp;
				}
			}
		}
	}
}

堆排序：

public class SortByHeap extends SortBase{

	public SortByHeap(){
		this.setTag(DataSource.SortHeap);
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		for( int i = data.length / 2; i >= 0; i--){
			adjustHeap(data, i, data.length);
		}
		int last = data.length - 1;
		int tmp = 0;
		while(last > 0){
			tmp = data[last];
			data[last] = data[0];
			data[0] = tmp;
			adjustHeap(data, 0, last);
			last--;
		}
	}

	public void adjustHeap(int[] data, int parent, int last){
		int max = parent;
		int tmp = 0;
		if(parent * 2 >= last){
			return ;
		}
		else if(parent * 2 < last && parent * 2 + 1 < last){
			if(data[parent * 2] > data[max]){
				max = parent * 2;
			}
			if(data[parent * 2 + 1] > data[max]){
				max = parent * 2 + 1;
			}
			if(max != parent){
				tmp = data[parent];
				data[parent] = data[max];
				data[max] = tmp;
				adjustHeap(data, max, last);
			}
		}
		else{
			if(data[parent * 2] > data[max]){
				max = parent * 2;
				tmp = data[parent];
				data[parent] = data[max];
				data[max] = tmp;
				adjustHeap(data, max, last);
			}
		}
	}
}

希尔排序

public class SortByHill extends SortBase{

	public SortByHill(){
		this.setTag("Hill");
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		int step = data.length / 2;
		int base = 0, i = 0, j = 0;
		while(step > 0){
			for( i = step; i < data.length; i++){
				base = data[i];
				for( j = i - step; j >= 0 && data[j] > base; j -= step){
					data[j + step] = data[j];
				}
				data[j + step] = base;
			}
			step = step / 2;
		}
	}

}

插入排序：

public class SortByInsert extends SortBase{
	
	public SortByInsert(){
		this.setTag("Insert");
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		int base = 0;
		int i = 0, j = 0;
		for( i = 1; i < data.length; i++){
			base = data[i];
			for(j = i - 1; j >= 0 && data[j] > base; j--){
				data[j + 1] = data[j];
			}
			data[j + 1] = base;
		}
	}

}

归并排序：

public class SortByMerge extends SortBase{

	public SortByMerge(){
		this.setTag(DataSource.SortMerge);
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		if(data.length == 1){
			return ;
		}
		else{
			int mid = data.length / 2;
			int[] leftData = new int[mid];
			int[] rightData = new int[data.length - mid];
			int i = 0, j = 0;
			for( i = 0; i < mid; i++){
				leftData[i] = data[i];
			}
			for( j = 0; j < data.length - mid; j++, i++){
				rightData[j] = data[i];
			}
			ownSort(leftData);
			ownSort(rightData);
			merge(data, leftData, rightData);
		}
	}
	
	private void merge(int[] data, int[] left, int[] right){
		int leftPos = 0, rightPos = 0, destPos = 0;
		while(leftPos < left.length && rightPos < right.length){
			if(left[leftPos] < right[rightPos]){
				data[destPos] = left[leftPos];
				leftPos++;
			}
			else{
				data[destPos] = right[rightPos];
				rightPos++;
			}
			destPos++;
		}
		if(leftPos >= left.length){
			while(rightPos < right.length){
				data[destPos] = right[rightPos];
				destPos++;
				rightPos++;
			}
		}
		if(rightPos >= right.length){
			while(leftPos < left.length){
				data[destPos] = left[leftPos];
				destPos++;
				leftPos++;
			}
		}
	}
}

快速排序：

public class SortByQuick extends SortBase{

	public SortByQuick(){
		this.setTag("Quick");
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		quickSort(data, 0, data.length - 1);
	}
	
	public void quickSort(int[] data, int left, int right){
		if(left < right){
			int mid = division(data, left, right);
			quickSort(data, left, mid - 1);
			quickSort(data, mid + 1, right);
		}
	}
	
	public int division(int[] data, int left, int right){
		int base = data[left];
		int tmp = 0;
		while(left < right){
			while(left < right && data[right] > base){
				right--;
			}
			while(left < right && data[left] < base){
				left++;
			}
			tmp = data[left];
			data[left] = data[right];
			data[right] = tmp;
		}
		data[left] = base;
		return left;
	}
}

数据类：

public class DataSource {
	public static int SIZE = 11;
	public static int[] getIntArray(){
		int[] dataArray = new int[SIZE];
		for(int i = 1; i < SIZE; i++){
			dataArray[i] = SIZE - i;
		}
		return dataArray;
	}
	
	public static void logs(String pLog){
		System.out.println("longs = " + pLog);
	}
	
	public static final String SortInsert = "Insert";
	public static final String SortBubble = "Bubble";
	public static final String SortQuick = "Quick";
	public static final String SortHill = "Hill";
	public static final String SortHeap = "Heap";
	public static final String SortMerge = "Merge";
}

默认不处理：

public class SortDefault extends SortBase{

	public SortDefault(){
		this.setTag("Default");
	}
	
	@Override
	public void ownSort(int[] data) {
		// TODO Auto-generated method stub
		
	}

}

测试代码：

public class TestSort {
	public static void main(String args[]) {
		TestSort testSort = new TestSort();
		testSort.test(DataSource.SortInsert);
		testSort.test(DataSource.SortBubble);
		testSort.test(DataSource.SortQuick);
		testSort.test(DataSource.SortHill);
		testSort.test(DataSource.SortHeap);
		testSort.test(DataSource.SortMerge);
	}
	
	public void test(String pString){
		SortBase sortBase = getProperSortBase(pString);
		sortBase.printArray();
		sortBase.loadBeginTime();
		sortBase.sort();
		sortBase.loadEndTime();
		sortBase.printDuration();
		sortBase.printArray();
	}
	
	public SortBase getProperSortBase(String pString){
		if(pString.equals(DataSource.SortBubble)){
			return new SortByBubble();
		}
		if(pString.equals(DataSource.SortQuick)){
			return new SortByQuick();
		}
		if(pString.equals(DataSource.SortInsert)){
			return new SortByInsert();
		}
		if(pString.equals(DataSource.SortHill)){
			return new SortByHill();
		}
		if(pString.equals(DataSource.SortHeap)){
			return new SortByHeap();
		}
		if(pString.equals(DataSource.SortMerge)){
			return new SortByMerge();
		}
		return new SortDefault();
	}
}

但设置每个排序名称的方法没有找到合适的地方，我的期望是在每个子类中去设置名称，但想不到好的办法就放在构造函数中了，不知道这个有什么好的处理办法没，如果有的话希望得到您的指点，当然如果发现有什么问题，希望得到您的指点，谢谢您。