0.排序基类 /** * 为了后面排序算法扩展的方便,引入一个基础类 Sorter */ package com.javasort; /** * 任何排序算法都继承此公共抽象基类 Sorter * @author Daniel Cheng * */ public abstract class Sorter
> { /** * 任何排序算法都重写此抽象方法 * @param array:欲排序的数组 * @param from:元素的起始下标 * @param len:数组的长度 */ public abstract void sort(E[] array, int from, int len); /** * 测试排序用例时调用此方法 * @param array */ public final void sort(E[] array) { sort(array, 0, array.length); } /** * 需要交换元素顺序时调用此方法 * @param array * @param from * @param to */ protected final void swap(E[] array, int from, int to) { E tmp = array[from]; array[from] = array[to]; array[to] = tmp; } /** * 打印排序后数组元素时调用此方法
* @param array */ public final void printResult(E[] array){ for(int i=0;i> extends Sorter { private static boolean DOWN = true; @Override public void sort(E[] array, int from, int len) { if (DOWN) { bubble_down(array, from, len); } else { bubble_up(array, from, len); } } private final void bubble_down(E[] array, int from, int len) { for(int i=from;ii;j--){ if(array[j]pareTo(array[j-1])<0){ swap(array, j-1, j);
} } } } private final void bubble_up(E[] array, int from, int len) { for(int i=from+len-1;i>=from;i--){ for(int j=from;j0){ swap(array, j, j+1); } } } } static final void up() { DOWN=false; } } /** * */ package com.javasort.bubblesorter; import com.javasort.Sorter; /** * @author Daniel Cheng * */ public class BubbleSorterTest { public static void main(String[] args) { Comparable[] array={5,1,13,2,17,9,7,4,0}; Sorter bubbleSorter=new BubbleSorter(); //BubbleSorter.up(); bubbleSorter.sort(array); bubbleSorter.printResult(array); }
} 2.插入法排序 package com.javasort.insertsorter; /** * 插入法排序在数据规模小的时候十分高效,该算法每次插入第 k+1 个元素到 * 前 k 个有序数组中一个合适的的位置(k=0...N-1) ,从而完成排序。 */ import com.javasort.Sorter; /** * @author Daniel Cheng * */ public class InsertSorter> extends Sorter { @Override public void sort(E[] array, int from, int len) { E temp=null; for(int i=from+1;i ++){ temp=array[i]; int j=i; for(;j>from;j--){ if(temppareTo(array[j-1])<0){ array[j]=array[j-1]; } else break; } array[j]=temp; } }
} package com.javasort.insertsorter; import com.javasort.Sorter; public class InsertSorterTest {
public static void main(String[] args) { Comparable[] array={5,1,13,2,14,9,7,4,0}; Sorter insertSort=new InsertSorter(); insertSort.sort(array); insertSort.printResult(array); } } 3.快速排序 package com.javasort.quicksorter; /** * 快速排序是目前使用可能最广泛的排序算法.一般分如下步骤: * 1)选择一个枢纽元素(有很对选法,我的实现里采用去中间元素的简单方法) * 2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并 把枢纽元素放在合适的位置。 * 3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己, 对左边的,右边的分别递归调用快速排序算法即可。 * 快速排序的核心在于分割算法,也可以说是最有技巧的部分。 */ import com.javasort.Sorter; /** * @author Daniel Cheng * */ public class QuickSorter> extends Sorter { @Override public void sort(E[] array, int from, int len) { q_sort(array, from, from + len - 1); } private final void q_sort(E[] array, int from, int to) { if (to - from < 1) return; int pivot = selectPivot(array, from, to); pivot = partion(array, from, to, pivot); q_sort(array, from, pivot - 1);
q_sort(array, pivot + 1, to); } private int partion(E[] array, int from, int to, int pivot) { E tmp = array[pivot]; array[pivot] = array[to];// now to's position is available while (from != to) { while (from < to &;&; array[from]pareTo(tmp) <= 0) from++; if (from < to) { array[to] = array[from];// now from's position is available to--; } while (from < to &;&; array[to]pareTo(tmp) >= 0) to--; if (from < to) { array[from] = array[to];// now to's position is available now from++; } } array[from] = tmp; return from; } private int selectPivot(E[] array, int from, int to) { return (from + to) / 2; } } /** * */ package com.javasort.quicksorter; import com.javasort.Sorter; import com.javasort.insertsorter.InsertSorter; /** * @author Daniel Cheng *
*/ public class QuickSorterTest { public static void main(String[] args) { Comparable[] array={5,1,13,2,14,9,7,4,0}; Sorter quickSorter=new QuickSorter(); quickSorter.sort(array); quickSorter.printResult(array); } } 4.选择排序 package com.javasort.selectsorter; /** * 选择排序:相对于冒泡来说,它不是每次发现逆序都交换,而是 * 在找到全局第 i 小的时候记下该元素位置,最后跟第 i 个元素交换, * 从而保证数组最终的有序。 * 相对与插入排序来说,选择排序每次选出的都是全局第 i 小的, * 不会调整前 i 个元素了。 */ import com.javasort.Sorter; /** * * @author Daniel Cheng * */ public class SelectSorter ble> extends Sorter { @Override public void sort(E[] array, int from, int len) { for (int i = 0; i < len; i++) { int smallest = i; int j = i + from; for (; j < from + len; j++) { if (array[j]pareTo(array[smallest]) < 0) { smallest = j; } } swap(array, i, smallest); }
} } package com.javasort.selectsorter; import com.javasort.Sorter; import com.javasort.bubblesorter.BubbleSorter; public class SelectSorterTest { public static void main(String[] args) { Comparable[] array={5,1,13,2,17,9,7,4,0}; Sorter selectSorter=new SelectSorter(); selectSorter.sort(array); selectSorter.printResult(array); } } 约瑟夫问题 import java.util.Scanner; public class Yue { public static void main(String[] args) { int j = 0; boolean temp = true; Scanner sc = new Scanner(System.in); System.out.print("请输入要排列的总数:"); int n = sc.nextInt(); System.out.print("请输入选择数的步长:"); int m = sc.nextInt(); System.out.print("请输入起始的数:"); int k = sc.nextInt(); int [] arr = new int [n]; for(int i=0;i } if(j==m){ System.out.print(arr+"\t"); arr = -1; j = 0; } if(i==n-1){ i=-1; } for(int o=0;o程序执行完毕!"); } } 九宫格问题 package com.bjsxt.array; import java.util.Scanner; public class Nine{ public static void main(String[]args){ Scanner scan = new Scanner(System.in); System.out.print("请输入一个大于等于 3 的奇数:"); int n = scan.nextInt(); if(n % 2 == 0 || n < 3){ System.out.println("输入的有问题"); System.exit(0); } int x = 0; int y = n / 2; int z = 1; int[][] a = new int[n][n]; a[0][n/2] = 1;
for(int i = 2;i <= n * n;i++){ x = x - z; y = y + z; if(x < 0 &;&; y > (n-1)){ x = x + 2; y = y - 1; a[x][y] = i; }else if(x < 0 &;&; y < n){ x = n - 1; a[x][y] = i; }else if(x >= 0 &;&; y > (n-1)){ y = 0; a[x][0] = i; }else if(a[x][y]!=0){ x = x + 2; y = y - 1; a[x]