递归

  1. 汉诺塔游戏

    1. public static void main(String[] args) {
    2.      while(true){
    3.          System.out.println("請輸入盘子个数：");
    4.          Scanner sc1=new Scanner(System.in);
    5.          String str1=sc1.nextLine();
    6.          System.out.println("請輸入柱子代号：");
    7.          Scanner sc=new Scanner(System.in);
    8.          String str=sc.nextLine();
    9.          char arr[] =str.toCharArray();
    10.          int i=Integer.valueOf(str1);
    11.          print(i,arr[0],arr[1],arr[2]);
    12.      }
    13.  }
    14.  /**
    15.   * 
    16.   * @param n 總共幾個盤子
    17.   * @param from  開始的柱子
    18.   * @param in    中間的柱子
    19.   * @param to    目標柱子
    20.   * @return
    21.   * 无论有多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子。
    22.   */
    23.  public static void  print(int n,char from,char in,char to){
    24.      if(n==0){
    25.          System.out.println("盘子正在准备中。。。。");
    26.      //只有一个盘子
    27.      }else if(n==1){
    28.          System.out.println("第"+n+"个盘子从"+from+"移到"+to);
    29.      //无论有多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子。
    30.      }else{
    31.          //移动上面的所有盘子到中间
    32.          print(n-1,from,to,in);
    33.          System.out.println("第"+n+"个盘子从"+from+"移到"+to);
    34.          //把上面的所有盘子从中间位置移到目标位置
    35.          print(n-1,in,from,to);
    36.      }
    37.  }

  2. 斐波那契数列（1，1，2，3，5，8，13……..）

    1. /**
    2. 打印第N项的数列
    3. @param n 第几项
    4. */
    5. public int Fibonacci(int n) {
    6.      if(n==0){
    7.          return 0;
    8.      }else if(n==1 || n==2){
    9.          return 1;
    10.      }else{
    11.          return Fibonacci(n-1)+Fibonacci(n-2);
    12.      }
    13.  }

    排序

    1. 冒泡排序：

    1. public static void main(String[] args) {
    2.      int arr[]={5,3,2,6,7,1,4,8,9};
    3.      Sort bs=new Sort();
    4.      System.out.println(Arrays.toString(arr));
    5.      bs.bubblr(arr);
    6.      System.out.println(Arrays.toString(arr));
    7.  }
    8. /**
    9.   * 冒泡排序
    10.   * @param arr 需要排序的数组
    11.   */
    12.  public void bubblr(int[] arr){
    13.      //排序的轮数
    14.      for (int i = 0; i < arr.length-1; i++) {
    15.          //排序的次数
    16.          for (int j = 0; j < arr.length-i-1; j++) {
    17.              if(arr[j] > arr[j+1]){
    18.                  int temp=arr[j];
    19.                  arr[j]=arr[j+1];
    20.                  arr[j+1]=temp;
    21.              }
    22.          }
    23.      }
    24.  }

    2. 快速排序：

    排序过程：

    5 3 2 6 7 1 4 8 9 : 取第一个为标准，第一回合从后往前找出一个标准数小的数，是4，所以将4和标准数兑换得 4 3 2 6 7 1 5 8 9：接着，从前往后找，找出一个比标准数5大的数字，是6，将5和6交换得： 4 3 2 5 7 1 6 8 9：接着，从后往前找，找出一个比标准数5小的数字，是1，将5和1交换得： 4 3 2 1 7 5 6 8 9：接着，从前往后找找，找出一个比标准数5大的数字，是7，将5和7交换得： 4 3 2 1 5 7 6 8 9 这时，比基准数小的数都在基准数前面；比基准数大的数都在基准数后面，所以本轮快排结束，剩下的就是对基准数左右两边的数列在分别进行上述步骤，直到各个区间只有一个数为止。

  1. public static void main(String[] args) {
  2.         int arr[]={5,3,2,6,7,1,4,8,9};
  3.         Sort bs=new Sort();
  4.         System.out.println(Arrays.toString(arr));
  5.         bs.quick(arr,0,arr.length-1);
  6.         System.out.println(Arrays.toString(arr));
  7.     }
  8. /**
  9.      * 快速排序
  10.      * @param arr    需要排序的数组
  11.      * @param start  开始的位置
  12.      * @param end    结束的位置
  13.      */
  14.     public void quick(int[] arr,int start,int end){
  15.         if(start < end){
  16.             //定一个标椎,将数组的第一个数字作为标准
  17.             int stand =arr[start];
  18.             //记录需要排序的下标
  19.             int low=start;//左边的下标
  20.             int high=end;//右边的下标
  21.             //循环找比标准数大的数和比标准小的数
  22.             while(low < high){
  23.                 //当一个数字比标准数字大的时候，往右排
  24.                 if(low < high && stand <= arr[high]){
  25.                     high--;
  26.                 }
  27.                 //使用右边的数字替换左边的数字
  28.                 arr[low]=arr[high];
  29.                 //当一个数字比标准数字小的时候，往左排
  30.                 if(low < high && arr[low] <= stand){
  31.                     low++;
  32.                 }
  33.                 //使用左边的数字替换右边的数字
  34.                 arr[high]=arr[low];
  35.             }
  36.             //把标准值赋给低所在的位置的元素
  37.             arr[low]=stand;
  38.             System.out.println(Arrays.toString(arr));
  39.             //处理标准左边的数字
  40.             quick(arr,start,low);
  41.             //处理标准右边的数字
  42.             quick(arr,low+1,end);
  43.         }
  44.     }

3. 插入排序：

排序过程：

5 3 2 6 7 1 4 8 9：取第二个数字为基准，将第二个和前一个比较，如果第二个小，则往前去一位，得： 3 5 2 6 7 1 4 8 9：接着下一个数字2，将2和前面的比较，大的往后走，小的往前去得： 2 3 5 6 7 1 4 8 9：再接着取下一个数字6，将6和前面的比较，大的往后走，小的往前去得： 2 3 5 6 7 1 4 8 9：再接着取下一个数字6，将6和前面的比较，大的往后走，小的往前去得： …. 1 2 3 4 5 6 7 8 9

  1. public static void main(String[] args) {
  2.         int arr[]={5,3,2,6,7,1,4,8,9};
  3.         Sort bs=new Sort();
  4.         System.out.println(Arrays.toString(arr));
  5.         bs.insertSort(arr);
  6.         System.out.println(Arrays.toString(arr));
  7. }
  8. /**
  9.      * 插入排序
  10.      * @param arr 要排序的数组
  11.      */
  12.     public void insertSort(int[] arr){
  13.         //遍历当前所有的数字，
  14.         for(int i =1;i<arr.length ; i++){
  15.             //如果当前的数字比前一个数字小
  16.             if(arr[i] < arr[i-1]){
  17.                 //将当前的数字存起来
  18.                 int temp=arr[i];
  19.                 int j;
  20.                 //遍历当前数字前面的所有数字
  21.                 for(j=i-1;j>=0&&arr[j]>temp;j--){
  22.                     //把前一个数字赋给后一个数字
  23.                     arr[j+1]=arr[j];
  24.                 }
  25.                 //把临时变量（外层循环的当前元素）赋给不满足条件的后一个元素
  26.                 arr[j+1]=temp;
  27.             }
  28.         }
  29.     }

4. 希尔排序：

排序过程

升序： 特点是分步长，通过减半得方式排序，步长依次减半 5 3 2 6 7 1 4 8 9： 先计算步长为4，由于是9个数字，所以分5次比较，有5和7比较，7和9比较，3和1比较，2 和4 比较，6和8比较，得： 5 1 2 6 7 3 4 8 9： 第二次步长为2，以步长为2进行排序，让5和2，2和7，7和4，4和9比较，1和6，6和3，3 和8进行比较，得： 1 2 3 4 5 6 7 8 9

  1. public static void main(String[] args) {
  2.         int arr[]={5,3,2,6,7,1,4,8,9};
  3.         Sort bs=new Sort();
  4.         System.out.println(Arrays.toString(arr));
  5.         bs.shellSort(arr);
  6.         System.out.println(Arrays.toString(arr));
  7. }
  8. /**
  9. * 希尔排序
  10. * @param arr 要排序的数组
  11. */
  12. public void shellSort(int[] arr){
  13.     int k=1;//排序次数
  14.     //遍历所有步长 d
  15.     for(int d=arr.length/2;d>0;d/=2){
  16.         //遍历所有元素
  17.         for (int i = d; i < arr.length; i++) {
  18.             //遍历本组中的所有元素
  19.             for(int j =i-d;j>=0;j-=d){
  20.                 //如果当前元素大于加上步长后的元素
  21.                 if(arr[j] > arr[j+d]){
  22.                     int temp =arr[j];
  23.                     arr[j]=arr[j+d];
  24.                     arr[j+d] =temp;
  25.                 }
  26.             }
  27.         }
  28.         System.out.println("第"+k+"次排序结果"+Arrays.toString(arr));
  29.         k++;
  30.     }
  31. }

5. 选择排序：

  2. public static void main(String[] args) {
  3.         int arr[]={5,3,2,6,7,1,4,8,9};
  4.         Sort bs=new Sort();
  5.         System.out.println(Arrays.toString(arr));
  6.         bs.shellSort(arr);
  7.         System.out.println(Arrays.toString(arr));
  8. }
  9. /**
  10. * 选择排序
  11. * @param arr 需要排序的数组
  12. */
  13. public void selectSort(int[] arr){
  14.     //遍历所有的数字
  15.     for (int i = 0; i < arr.length; i++) {
  16.         int minIndex=i;//记录最小的数字的下标
  17.         //循环最小下标后面的数字
  18.         for (int j = i; j < arr.length; j++) {
  19.             //如果后面的数字比最小下标数字还小，就将最小数字的小标换成这个小标
  20.             if(arr[minIndex] > arr[j]){
  21.                 //记录最小数字的下标
  22.                 minIndex=j;
  23.             }
  24.         }
  25.         //如果最小下标和当前数字的小标不一致，说明下标minIndex的数比当前遍历的数更小
  26.         if(minIndex != i){
  27.             int temp=arr[i];
  28.             arr[i]=arr[minIndex];
  29.             arr[minIndex] =temp;
  30.         }
  31.     }
  32. }