未完待续
public class SortDemoMain { public static void main(String[] args){ int array[] = {6,21,9,16,55,4,41,27}; print(array); SortAlgorithm insertSort = new InsertSort(array); insertSort.sort(); print(array); SortAlgorithm bubbleSort = new BubbleSort(array); bubbleSort.sort(); print(array); SortAlgorithm selectSort = new SelectSort(array); selectSort.sort(); print(array); SortAlgorithm quickSort = new QuickSort(array); quickSort.sort(); quickSort.sort(0, array.length - 1); print(array); } public static void print(int array[]){ int i = 0; if (0 == array.length){ System.out.println("Invalid array"); return; } for (; i < array.length - 1; i++){ System.out.print(array[i] + ","); } System.out.printf("%d%n",array[i]); } } class SortAlgorithm{ protected int array[]; protected SortAlgorithm(int array[]){ this.array = array; } protected void sort(){ //入参不用再传入array，直接使用成员变量，成员变量在父类构造方法中赋值 System.out.print("[SortAlgorithm]"); } protected void sort(int i, int j) { System.out.print("[SortAlgorithm]"); } } class InsertSort extends SortAlgorithm{ protected InsertSort(int array[]){ super(array); //调用父类的构造方法,获取父类属性array } @Override protected void sort(){ super.sort(); System.out.print("InsertSort : "); int small = 0; int smallIndex = 0; for (int i = 0; i < array.length-1; i++) { if (array[i] > array[i+1]){ //外层循环以从左到右-->的方向，从第二个值开始，根据大小关系选取基准值 small = array[i+1]; //选小值作为基准值并记下其起始位置，以备左移 smallIndex = i+1; while(smallIndex > 0 && array[smallIndex-1] > small) { //内层循环以从右到左<--的方向，从基准值的位置开始逐一与其左值比较 array[smallIndex] = array[smallIndex-1];//基准值左边的大值逐一右移 smallIndex--; } array[smallIndex] = small; //大值右移后空下的位置放基准值 } } } } class BubbleSort extends SortAlgorithm{ protected BubbleSort(int[] array) { super(array); } @Override protected void sort() { super.sort(); System.out.print("BubbleSort : "); int tmp = 0; for (int trip = 0; trip < array.length-1; trip++) { //有n个元素就有n-1轮比较 for (int index = 0; index < array.length-trip-1; index++) {//本轮最大元素移到本轮参与元素的最右 if (array[index] > array[index+1]){ //避免对前几轮最右元素重复比较（一轮对应一个） tmp = array[index+1]; //每轮从左开始向右比较相邻元素，左大右小则互换 array[index+1] = array[index]; array[index] = tmp; } } } } } class SelectSort extends SortAlgorithm{ protected SelectSort(int[] array) { super(array); } @Override protected void sort() { super.sort(); System.out.print("SelectSort : "); int k = 0; int i = 0; int tmp = 0; for (int trip = 0; trip < array.length; trip++) {//起始值左边为有序序列（含起始值） tmp = array[trip]; k = trip;//此行易漏掉，造成右边没有更小值时k值未更新。 //如果有更小值，则此元素与更小值互换，如果没有更小值，则自己与自己换(或控制不换) for (i = trip+1; i < array.length; i++) {//从此轮起始值的右边（不含起始值）找出最小值的位置 if (tmp > array[i]){ tmp = array[i]; k = i; } } if (k != trip){ tmp = array[trip]; //将起始值右边的最小值与起始值互换，此轮最小值换到有序序列末尾 array[trip] = array[k]; array[k] = tmp; } } } } class QuickSort extends SortAlgorithm{ protected QuickSort(int[] array) { super(array); } @Override protected void sort() { super.sort(); System.out.print("QuickSort : "); } @Override protected void sort(int low, int high){ int base; if (low >= high){ return; } base = divideByPivot(low, high); sort(low, base - 1); sort(base + 1, high); } private int divideByPivot(int left, int right){ int pivot = array[left]; while (left < right){ //选取最左边为pivot，则从最右边开始比较 while (left < right && array[right] >= pivot){//若右边值大于pivot，则继续右边的下一个值比较 right --; } array[left] = array[right];//array[left]的原始值已经保存在pivot，不会被覆盖而丢失 //left ++; //左边新赋值后，接着从左边比较 while (left < right && array[left] <= pivot){//若左边值小于pivot，则继续左边的下一个值比较 left ++; } array[right] = array[left];//array[right]的原始值已经保存在array[left]，不会被覆盖而丢失 //right --; //右边新赋值后，接着从右边比较 } array[left] = pivot;//跳出外层while时left == right return left; } }
