排序类

/**
 * 定义数字排序的接口
 *
 */
public interface ISortNumber 
{
	/**
	 * 对整型数组按升序排序
	 * @param intArray 待排序的整型数组
	 * @return 按升序排序后的数组
	 */
	public int[] sortASC(int[] intArray);
}

/**
 * 
 * 使用选择排序法对整型数组进行排序
 */
public class SelectionSort implements ISortNumber 
{

	public int[] sortASC(int[] intArray) 
	{
		if(intArray == null)
		{
			return null;
		}
		/*
		 * 因为Java的参数传递是采用引用传值方式，在排序的过程中需要改变
		 * 数组元素的顺序，也就是改变了参数数组，所以，为了保证输入参数
		 * 的值不变，这里就采用了数组的clone方法，直接克隆一个数组
		 */
		
		int[] srcDatas = (int[])intArray.clone();
		int size = srcDatas.length;
		//从头遍历数组
		for(int i=0;i<size;i++)
		{
			//遍历下标威i之后的元素
			for(int j=i;j<size;j++)
			{
				//如果数组前面的值比后面的值大，则交换位置
				if(srcDatas[i]>srcDatas[j])
				{
					swap(srcDatas, i, j);
				}
			}
		}
		return srcDatas;
	}
	
	/**
	 * 交换数组中下标为src和dest的值
	 * @param data 数组
	 * @param src 源下标
	 * @param dest 目标下标
	 */
	private void swap(int[] data,int src,int dest)
	{
		int temp = data[src];
		data[src] = data[dest];
		data[dest] = temp;
	}

}

/**
 * 
 * 冒泡法对整型数组排序
 */
public class BubbleSort implements ISortNumber
{

	public int[] sortASC(int[] intArray) {
		if(intArray==null)
		{
			return null;
		}
		int[] srcDatas = (int[])intArray.clone();
		boolean changedPosition = true;	//标示是否交换了数组中元素位置
		int comparedTimes = 0;	//标示比较次数
		int maxComparedTimes = srcDatas.length-1;	//标示排序过程中最多可能交换的次数
		//如果已经发生的比较次数还没有到达最大次数，而且此前交换过元素位置，则继续
		while((comparedTimes<maxComparedTimes) && (changedPosition))
		{
			for(int i=0;i<(maxComparedTimes-comparedTimes);i++)
			{
				changedPosition=false;
				if(srcDatas[i]>srcDatas[i+1])
				{
					swap(srcDatas, i, i+1);
					changedPosition=true;
				}
			}
			comparedTimes++;
		}
		return srcDatas;
	}

	/**
	 * 交换数组中下标为src和dest的值
	 * @param data 数组
	 * @param src 源下标
	 * @param dest 目标下标
	 */
	private void swap(int[] data,int src,int dest)
	{
		int temp = data[src];
		data[src] = data[dest];
		data[dest] = temp;
	}
}

/**
 * 采用线性插入排序法实现数组排序
 *
 */
public class LinearInsertSort implements ISortNumber
{
	public LinearInsertSort()
	{
		
	}
	public int[] sortASC(int[] intArray) {
		if(intArray==null)
		{
			return null;
		}
		int[] srcDatas = (int[])intArray.clone();
		int size = srcDatas.length;
		int temp = 0;
		int index = 0;
		//假定第一个数字已经排好了顺序，所以i是从1开始而不是从0开始
		for(int i=1;i<size;i++)
		{
			temp = srcDatas[i];
			index = i;
			while((index>0) && (temp<srcDatas[index-1]))
			{
				//移动index后面的数字
				srcDatas[index] = srcDatas[index-1];
				index--;
			}
			srcDatas[index] = temp;
		}
		return srcDatas;
	}

}

/**
 * 采用快速排序法实现数组的排序
 *
 */
public class QuickSort implements ISortNumber
{
	public QuickSort()
	{
		
	}
	public int[] sortASC(int[] intArray) {
		if(intArray ==null)
		{
			return null;
		}
		int[] srcDatas = (int[])intArray.clone();
		return this.quickSort(srcDatas, 0, srcDatas.length-1);
	}
	
	/**
	 * 采用分治递归的方法实现快速排序法
	 * @param srcDatas 待排序的数组
	 * @param first 起始下标
	 * @param last 终止下标
	 * @return 排好序的数组
	 */
	private int[] quickSort(int[] srcDatas,int first,int last)
	{
		if(first<last)
		{
			int pos = partition(srcDatas, first, last);
			quickSort(srcDatas, first, pos-1);
			quickSort(srcDatas, pos+1, last);
		}
		return srcDatas;
	}
	
	/**
	 * 寻找数组的分治点
	 * 根据数组的第一个数分治，把比数组第一个数大的往后排，把比数组第一个数小的往前排
	 * @param srcDatas 待排序的数组
	 * @param first 起始下标
	 * @param last 终止下标
	 * @return 传入数组的第一个数的最终下标
	 */
	private int partition(int[] srcDatas,int first,int last)
	{
		int temp = srcDatas[first];
		int pos = first;
		for(int i=first+1;i<=last;i++)
		{
			if(srcDatas[i]<temp)
			{
				pos++;
				swap(srcDatas, pos, i);
			}
		}
		swap(srcDatas, first, pos);
		return pos;
	}
	
	/**
	 * 交换数组中下标为src和dest的值
	 * @param data
	 * @param src
	 * @param dest
	 */
	private void swap(int[] data,int src,int dest)
	{
		int temp = data[src];
		data[src] = data[dest];
		data[dest] = temp;
	}
}

public class SortTest 
{
	/**
	 * 打印数组
	 * @param intArray
	 */
	public static void printIntArray(int[] intArray)
	{
		if(intArray==null)
		{
			return;
		}
		for(int i=0;i<intArray.length;i++)
		{
			System.out.print(intArray[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args)
	{
		int[] intArray = new int[]{6,3,4,2,7,2,-3,3};
		
		System.out.print("排序前的数组：");
		printIntArray(intArray);
		ISortNumber test = new SelectionSort();
		System.out.print("选择排序法排序结果：");
		printIntArray(test.sortASC(intArray));
		
		System.out.print("排序前的数组：");
		printIntArray(intArray);
		test = new BubbleSort();
		System.out.print("冒泡排序法排序结果：");
		printIntArray(test.sortASC(intArray));
		
		System.out.print("排序前的数组：");
		printIntArray(intArray);
		test = new LinearInsertSort();
		System.out.print("线性插入排序法排序结果");
		printIntArray(test.sortASC(intArray));
		
		System.out.print("排序前的数组：");
		printIntArray(intArray);
		test = new QuickSort();
		System.out.print("快速排序法排序结果");
		printIntArray(test.sortASC(intArray));
	}
}