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