排序种

排序类

/** * 定义数字排序的接口 * */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));}}