递归

介绍

简单的说：递归就是方法自己刁颖自己，每次调用传入不同的变量，递归有助于编程者解觉复杂的问题，同时可以让代码变得简洁

递归应用场景

  1. 数学问题：迷宫问题、8皇后问题、汉诺塔、阶乘问题、球和篮子问题等等
  2. 算法问题：快排、归并排序、二分查找、分治算法等

递归调用机制

  1. 打印问题 ```java public class TestMain {

    public static void main(String[] args) {

    1.  test(4);

    }

    public static void test(int n) {

    1.  if (n > 2) {
    2.      test(n-1);
    3.  }
    4.  System.out.println("n = " + n);

    }

}

  2. 2. 阶乘问题
  3. ```java
  4. public class TestMain {
  6.     public static void main(String[] args) {
  8.         System.out.println(test1(5));
  10.     }
  12.     public static int test1(int n) {
  13.         if (n == 1) {
  14.             return 1;
  15.         }
  16.         return test1(n - 1) * n;
  17.     }
  19. }

递归需要遵守的重要规则

  1. 执行一个方法时，就创建一个新的受保护的独立空间（栈空间）
  2. 方法的局部变量是独立的，不会相互影响
  3. 如果方法中使用的是引用类型变量，就会共享该引用类型的数据
  4. 递归必须向退出递归条件逼近，否则就是无限递归（StackOverflowError）
  5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法就执行完毕

迷宫回溯问题分析和实现

  1. 简单找路迷宫 ```java public class MiGong {

    public static void main(String[] args) {

    1.  //先创建一个二维数组，模拟迷宫
    2.  //地图
    3.  int[][] map = new int[8][7];
    4.  //使用1表示迷宫的墙
    5.  //先把上下全部置为1
    6.  for (int i = 0; i < 7; i++) {
    7.      map[0][i] = 1;
    8.      map[7][i] = 1;
    9.  }
    10.  //把左右全部置为1
    11.  for (int i = 0; i< 8; i++) {
    12.      map[i][0] = 1;
    13.      map[i][6] = 1;
    14.  }
    15.  //设置除外墙之外的内墙
    16.  map[3][1] = 1;
    17.  map[3][2] = 1;
    18.  //输出地图
    19.  for (int i = 0; i < 8; i++) {
    20.      for (int j = 0; j < 7; j++) {
    21.          System.out.print(map[i][j] + " ");
    22.      }
    23.      System.out.println();
    24.  }
    26.  //使用递归回溯，找路
    27.  setWay(map,1,1);
    28.  System.out.println("-----------------------");
    30.  //输出路径图
    31.  for (int i = 0; i < 8; i++) {
    32.      for (int j = 0; j < 7; j++) {
    33.          System.out.print(map[i][j] + " ");
    34.      }
    35.      System.out.println();
    36.  }

    }

    //使用递归来走迷宫 //1. map表示地图 //2. i，j表示从地图的哪个位置开始出发：例如(1,1) //3. 如果小球能到达map[6][5]位置，则说明通路能找到 //4. 当map[i][j]为0表示该点没有走过，当为1表示墙，2表示通路可以走，3表示该点已经走过，但是走不通 //5. 在走迷宫时需要确定一个策略，下->右->上->左

    /*

    • @param map 表示地图
    • @param i 从地图的i行开始
    • @param j 从地图的j列开始
    • @return 如果找到则返回true，否则返回false */ public static boolean setWay(int[][] map, int i, int j) { if (map[6][5] == 2) { //通路已经找到ok
      1.  return true;
      } else {
      1.  if (map[i][j] == 0) { //如果当前这个点还没有走过
      2.      //下->右->上->左
      3.      map[i][j] = 2; //假定该点可以走通
      4.      if (setWay(map, i + 1, j)) { //下
      5.          return true;
      6.      } else if (setWay(map, i, j + 1)) { //右
      7.          return true;
      8.      } else if (setWay(map, i - 1, j)) { //上
      9.          return true;
      10.      } else if (setWay(map, i, j - 1)) { //左
      11.          return true;
      12.      } else {
      13.          //说明是死路
      14.          map[i][j] = 3;
      15.          return false;
      16.      }
      17.  } else { //如果map[i][j] != 0，可能是1,2,3
      18.      return false;
      19.  }
      } }

}

  2. 2. 找出迷宫的所有路径
  3. ```java
  4. import java.io.BufferedReader;
  5. import java.io.FileNotFoundException;
  6. import java.io.FileReader;
  7. import java.io.IOException;
  9. public class MyMiGong {
  11.     //读取迷宫的规格
  12.     final static int HEIGHT = 7;
  13.     final static int WIDTH = 7;
  15.     public static void main(String[] args) throws IOException {
  17.         //迷宫文件路径
  18.         String mapFile = "Recursion/src/maps/map1.txt";
  20.         int[][] map = readMap(mapFile);
  22.         System.out.println("-------迷宫-------");
  23.         for (int[] ints : map) {
  24.             for (int anInt : ints) {
  25.                 System.out.print(anInt + " ");
  26.             }
  27.             System.out.println();
  28.         }
  30.         findWay(map, 1, 1);
  32.     }
  34.     /**
  35.      *
  36.      * @param mapFile 文件路径字符串
  37.      * @return 迷宫地图
  38.      * @throws IOException
  39.      */
  40.     public static int[][] readMap(String mapFile) throws IOException {
  42.         int[][] map = new int[HEIGHT][WIDTH];
  44.         BufferedReader br = new BufferedReader( new FileReader(mapFile));
  46.         String buff = null;
  47.         int i = 0;
  48.         while ( (buff = br.readLine() ) != null ) {
  49.             for (int j = 0; j < buff.length(); j++) {
  50.                 map[i][j] = Integer.parseInt(String.valueOf(buff.charAt(j)));
  51.             }
  52.             i++;
  53.         }
  55.         return map;
  56.     }
  58.     public static void findWay(int[][] map, int i, int j) {
  60.         map[i][j] = 2;
  62.         if (i == 5 && j == 5) {
  63.             System.out.println("-------路径-------");
  64.             for (int[] ints : map) {
  65.                 for (int anInt : ints) {
  66.                     System.out.print(anInt + " ");
  67.                 }
  68.                 System.out.println();
  69.             }
  70.         }
  72.         //向上移动
  73.         if (map[i - 1][j] == 0) {
  74.             findWay(map,i-1, j);
  75.         }
  76.         //向左移动
  77.         if (map[i][j - 1] == 0) {
  78.             findWay(map, i, j-1);
  79.         }
  80.         //向下移动
  81.         if (map[i + 1][j] == 0) {
  82.             findWay(map,i+1, j);
  83.         }
  84.         //向右移动
  85.         if (map[i][j + 1] == 0) {
  86.             findWay(map,i, j+1);
  87.         }
  89.         map[i][j] = 0;
  91.     }
  93. }

1. 八皇后问题（回溯算法）

八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋于马克斯·贝瑟尔于1848年提出，在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能在同一行、同一列或同一斜线上，问有多少种摆法。存在92种

思路分析

  1. 第一个皇后先放在第一列第一行
  2. 第二个皇后放在第二行第一列，然后判断是否满足条件，如果不满足，继续放在第二列、第三列，依次把所有列都放完，找到一个合适的
  3. 继续第三个皇后，还是第一列、第二列…直到第八个皇后也能放在一个不冲突的位置，算是找到一个正确的解
  4. 当得到一个正确解时，在栈回退到上一个栈，就开始回溯，即将第一个皇后，放到第一列的所有解，全部得到
  5. 然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4的步骤
  6. 补充：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法用一个一维数组即可解决该问题，如arr[8] = {0,4,7,5,2,6,1,3}，arr的下标n表示第n+1行，即也是第n+1个皇后，n所指向的数d表示第d+1列

代码实现

  1. package queen8;
  3. import java.util.Arrays;
  5. public class Queen8 {
  7.     //皇后个数
  8.     final static int QUEEN = 8;
  9.     //定义数组array，保存皇后的放置位置的结果，比如arr = {0,4,7,5,2,6,1,3}
  10.     int[] array = new int[QUEEN];
  11.     //计数
  12.     static int count = 0;
  14.     public static void main(String[] args) {
  15.         Queen8 queen8 = new Queen8();
  16.         queen8.check(0);
  17.     }
  19.     //编写一个方法，放置第n个皇后
  20.     private void check(int n) {
  21.         if (n == QUEEN) {
  22.             System.out.println(++count + ": " + Arrays.toString(array));
  23.             return;
  24.         }
  26.         //依次放入皇后,并判断是否冲突
  27.         for (int i = 0; i < QUEEN; i++) {
  28.             //将皇后n，放到第n行第i列
  29.             array[n] = i;
  30.             //判断是否冲突
  31.             if (judge(n)) { //不冲突
  32.                 //则方n+1的皇后
  33.                 check(n + 1);
  34.             }
  35.             //冲突则放到下一列
  36.         }
  37.     }
  39.     //查看当我们放置第n个皇后，就去检测该皇后是否和前面已经放置的皇后出图
  40.     private boolean judge(int n) {
  41.         for (int i = 0; i < n; i++) {
  42.             //array[i] == array[n]  判断第n个皇后是否和前面的n-1个皇后在同一列
  43.             //Math.abs(n - i) == Math.abs(array[n] - array[i])  判断第n个皇后是否和第i个皇后在同一斜线上
  44.             if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
  45.                 return false;
  46.             }
  47.         }
  48.         return true;
  49.     }
  51. }

排序

介绍

排序也称排序算法（Sort Algorithm），排序是将一组数据，依指定的顺序进行排序的过程

排序的分类

  1. 内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序
  2. 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

常见的排序算法分类

  1. 内部排序
    • 插入排序：直接插入排序、希尔排序(Shell排序)
    • 选择排序：简单选择排序、堆排序
    • 交换排序：冒泡排序、快速排序
    • 归并排序
    • 基数排序
  2. 内部排序

算法的时间复杂度

  1. 度量一个程序（算法）执行时间的两种方法
    • 事后统计法
    • 事前估计法
  2. 时间频度
    • 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行的次数多，它花费时间就越多
    • 一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)
    • 举例 ```java int toltal = 0; int end = 100; //使用for循环计算 for (int i = 1; i <= end; i++) { total+=1; }

//计算出时间赋值T(n) = n + 1

  2.    - **忽略常数项、忽略低次项、忽略系数**
  3. 3. 时间复杂度
  4.    - 一般情况下，算法中的基本操作语句的重复执行次数是规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度
  5.    - 时间频度不同，但时间复杂度是可能相同的
  6.    - 计算时间复杂度的方法
  7.       - 用常数1代替运行时间中的所有加法常数
  8.       - 修改后的运行次数函数中，只保留最高阶项
  9.       - 去除最高阶项的系数
  10. 4. 常见的时间复杂度（**由小到大**：随着问题规模n的不断增大，以下时间复杂度不断增大，算法执行的效率越低）
  11.    - 常数阶O(1)
  12.    - 对数阶O(logn)
  13.    - 线性阶O(n)
  14.    - 线性对数阶O(nlogn)
  15.    - 平方阶O(n)
  16.    - 立方阶O(n)
  17.    - k次方阶O(n)
  18.    - 指数阶O(2)
  19. 5. 平均时间复杂度和最坏时间复杂度
  20.    - 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况，该算法的运行时间
  21.    - 最坏情况下的时间复杂度称为最坏时间复杂度，**一般讨论时间复杂度都是最坏情况下的时间复杂度**，是因为最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长
  22.    - 平均时间复杂度和最坏时间复杂度是否一致，和算法有关，如下表
  23. | 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
  24. | :---: | :---: | :---: | :---: | :---: | :---: |
  25. | 冒泡排序 | O(n) | O(n) | 稳定 | O(1) | n小时较好 |
  26. | 交换排序 | O(n) | O(n) | 不稳定 | O(1) | n小时较好 |
  27. | 选择排序 | O(n) | O(n) | 不稳定 | O(1) | n小时较好 |
  28. | 插入排序 | O(n) | O(n) | 稳定 | O(1) | 大部分已排序时较好 |
  29. | 基数排序 | O(log) | O(log) | 稳定 | O(n) | B是真数(0-9)，R是基数(个十百) |
  30. | 希尔排序 | O(nlogn) | O(n) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
  31. | 快速排序 | O(nlogn) | O(n) | 不稳定 | O(nlogn) | n大时较好 |
  32. | 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
  33. | 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
  36. <a name="15208fbb"></a>
  37. ## 算法的空间复杂度
  39. 1. 类似于时间复杂度的谈论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数
  40. 1. 空间复杂度是一个算法在运行过程中临时占用存储空间大小的度量，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序就属于这种情况
  41. 1. 在做算法分析时，主要讨论的是算法时间复杂度，从用户的角度来看，更看重程序的执行速度，
  42. 1. 一些缓存产品和算法本质就是用**空间换时间**
  44. <a name="bdb1d069"></a>
  45. ## 1. 冒泡排序(Bubble Sort)
  47. <a name="0a480a91"></a>
  48. ### 冒泡排序介绍
  50. 1. 冒泡排序的基本思想是：通过对待排序序列从前向后（从下表较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
  51. 1. **优化**：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过减缓，从而减少不必要的比较
  53. <a name="83175ad0-1"></a>
  54. ### 代码实现
  56. 1. 基本实现
  58. ```java
  59. package bubblesorting;
  61. import java.util.Arrays;
  63. public class BubbleSorting {
  65.     public static void main(String[] args) {
  67.         //定义需要排序的数组
  68.         int arr[] = {3,9,-1,10,-2};
  69.         //int arr[] = {2,1,3,4,5};
  70.         //定义交换数
  71.         int temp = 0;
  72.         //定义优化变量
  73.         boolean flag;
  75.         for (int i = 0; i < arr.length - 1; i++) {
  76.             flag = true;
  77.             for (int j = 0; j < arr.length - 1 - i; j++) {
  78.                 //如果前面的数比后面的数大，则交换
  79.                 if (arr[j] > arr[j + 1]) {
  80.                     temp = arr[j];
  81.                     arr[j] = arr[j + 1];
  82.                     arr[j + 1] = temp;
  83.                     flag = false;
  84.                 }
  85.             }
  86.             System.out.println("第"+ (i+1) +"排序");
  87.             System.out.println(Arrays.toString(arr));
  88.             if (flag) {
  89.                 break;
  90.             }
  91.         }
  93.     }
  95. }
  1. 封装成方法以及观察冒泡排序的运行速度
  1. package bubblesorting;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  6. public class BubbleSorting {
  8.     public static void main(String[] args) {
  10.         //测试一下冒泡排序的速度O(n^2)，给80000个数据，测试
  11.         //创建存在80000个随机数的数组
  12.         int[] arr = new int[80000];
  13.         for (int i = 0; i < arr.length; i++) {
  14.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  15.         }
  17.         Date date1 = new Date();
  18.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  19.         String date1Str = simpleDateFormat.format(date1);
  20.         System.out.println("排序前的时间是: " + date1Str);
  22.         bubbleSort(arr);
  24.         Date date2 = new Date();
  25.         String date2Str = simpleDateFormat.format(date2);
  26.         System.out.println("排序后的时间是: " + date2Str);
  28.         System.out.println("总共消耗时间约为：" + ((date2.getTime() - date1.getTime()) / 1000) + "秒");
  31.     }
  33.     public static void bubbleSort(int[] arr) {
  34.         //定义交换数
  35.         int temp = 0;
  36.         //定义优化变量
  37.         boolean flag;
  39.         for (int i = 0; i < arr.length - 1; i++) {
  40.             flag = true;
  41.             for (int j = 0; j < arr.length - 1 - i; j++) {
  42.                 //如果前面的数比后面的数大，则交换
  43.                 if (arr[j] > arr[j + 1]) {
  44.                     temp = arr[j];
  45.                     arr[j] = arr[j + 1];
  46.                     arr[j + 1] = temp;
  47.                     flag = false;
  48.                 }
  49.             }
  50.             if (flag) {
  51.                 break;
  52.             }
  53.         }
  55.     }
  57. }

2. 选择排序(Select Sort)

选择排序介绍

  1. 选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
  2. 选择排序思想是：第1次从arr[0]到arr[n-1]中选取最小值，与arr[0]交换，第2次再从arr[1]到[n-1]中选取最小值，与arr[1]交换，…，第i次从arr[i]到[n-1]中选取最小值，与arr[i]交换，…，第n-1次从arr[n-2]到arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排序的有序序列。通俗来讲就是把每次找到的最小值与最前面（这里的最前面是指除前面找找到排好的）的那个数交换。

代码实现

  1. 基本实现
  1. package selectsorting;
  3. import java.util.Arrays;
  5. public class SelectSorting {
  7.     public static void main(String[] args) {
  9.         int[] arr = {101,34,119,1};
  11.         System.out.println("排序前：" + Arrays.toString(arr));
  13.         selectSort(arr);
  15.         System.out.println("排序后：" + Arrays.toString(arr));
  17.     }
  19.     public static void selectSort(int[] arr) {
  21.         //用来交换的数
  22.         int temp;
  23.         //记录着数组中最小值得下标
  24.         int minIndex;
  26.         for (int i = 0; i < arr.length - 1; i++) {
  27.             minIndex = i;
  28.             for (int j  = i + 1; j < arr.length; j++) {
  29.                 if (arr[j] < arr[minIndex]) {
  30.                     //得到最小值得下标
  31.                     minIndex = j;
  32.                 }
  33.             }
  34.             //进行数据交换(优化)
  35.             if (minIndex != i) {
  36.                 temp = arr[i];
  37.                 arr[i] = arr[minIndex];
  38.                 arr[minIndex] = temp;
  39.             }
  40.         }
  42.     }
  44. }
  1. 运行速度测试
  1. package selectsorting;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  6. public class SelectSorting {
  8.     public static void main(String[] args) {
  10.         int[] arr = new int[80000];
  11.         for (int i = 0; i < arr.length; i++) {
  12.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  13.         }
  15.         Date date1 = new Date();
  16.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  17.         String date1Str = simpleDateFormat.format(date1);
  18.         System.out.println("排序前的时间是: " + date1Str);
  20.         selectSort(arr);
  22.         Date date2 = new Date();
  23.         String date2Str = simpleDateFormat.format(date2);
  24.         System.out.println("排序后的时间是: " + date2Str);
  26.         System.out.println("总共消耗时间约为：" + ((date2.getTime() - date1.getTime()) / 1000) + "秒");
  28.     }
  30.     public static void selectSort(int[] arr) {
  32.         //用来交换的数
  33.         int temp;
  34.         //记录着数组中最小值得下标
  35.         int minIndex;
  37.         for (int i = 0; i < arr.length - 1; i++) {
  38.             minIndex = i;
  39.             for (int j  = i + 1; j < arr.length; j++) {
  40.                 if (arr[j] < arr[minIndex]) {
  41.                     //得到最小值得下标
  42.                     minIndex = j;
  43.                 }
  44.             }
  45.             //进行数据交换(优化)
  46.             if (minIndex != i) {
  47.                 temp = arr[i];
  48.                 arr[i] = arr[minIndex];
  49.                 arr[minIndex] = temp;
  50.             }
  51.         }
  53.     }
  55. }

3. 插入排序(Insertion Sort)

插入排序介绍

  1. 插入式排序属于内部排序法，是对于欲排序的元素插入的方式找寻该元素的适当位置，以达到排序的目的。
  2. 插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

代码实现

  1. 基本实现
  1. package insertsorting;
  3. import java.util.Arrays;
  5. public class InsertSorting {
  7.     public static void main(String[] args) {
  9.         int[] arr = {101,34,119,1};
  11.         System.out.println("排序前:" + Arrays.toString(arr));
  13.         insertSort(arr);
  15.         System.out.println("排序后:" + Arrays.toString(arr));
  17.     }
  19.     public static void insertSort(int[] arr) {
  21.         int temp;
  22.         int tempIndex;
  24.         for (int i = 1; i < arr.length; i++) {
  25.             temp = arr[i];
  26.             tempIndex = i - 1;
  27.             while(tempIndex >= 0 && temp < arr[tempIndex]) {
  28.                 arr[tempIndex + 1] = arr[tempIndex];
  29.                 tempIndex--;
  30.             }
  31.             arr[tempIndex + 1] = temp;
  32.         }
  34.     }
  36. }
  1. 运行速度测试
  1. package insertsorting;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  6. public class InsertSorting {
  8.     public static void main(String[] args) {
  10.         int[] arr = new int[80000];
  11.         for (int i = 0; i < arr.length; i++) {
  12.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  13.         }
  15.         Date date1 = new Date();
  16.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  17.         String date1Str = simpleDateFormat.format(date1);
  18.         System.out.println("排序前的时间是: " + date1Str);
  20.         insertSort(arr);
  22.         Date date2 = new Date();
  23.         String date2Str = simpleDateFormat.format(date2);
  24.         System.out.println("排序后的时间是: " + date2Str);
  26.         System.out.println("总共消耗时间约为：" + ((date2.getTime() - date1.getTime()) / 1000) + "秒");
  28.     }
  30.     public static void insertSort(int[] arr) {
  32.         int temp;
  33.         int tempIndex;
  35.         for (int i = 1; i < arr.length; i++) {
  36.             temp = arr[i];
  37.             tempIndex = i - 1;
  38.             while(tempIndex >= 0 && temp < arr[tempIndex]) {
  39.                 arr[tempIndex + 1] = arr[tempIndex];
  40.                 tempIndex--;
  41.             }
  42.             arr[tempIndex + 1] = temp;
  43.         }
  45.     }
  47. }

4. 希尔排序(Shell Sort)

希尔排序介绍

  1. 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
  2. 希尔排序的基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

代码实现

  1. 交换法
  1. package shellsorting;
  3. import java.util.Arrays;
  5. public class ShellSorting {
  7.     public static void main(String[] args) {
  9.         //int[] arr = {8,9,1,7,2,3,5,4,6,0};
  11.         int[] arr = new int[80000];
  12.         for (int i = 0; i < arr.length; i++) {
  13.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  14.         }
  16.         Date date1 = new Date();
  17.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  18.         String date1Str = simpleDateFormat.format(date1);
  19.         System.out.println("排序前的时间是: " + date1Str);
  21.         shellSort1(arr);
  23.         Date date2 = new Date();
  24.         String date2Str = simpleDateFormat.format(date2);
  25.         System.out.println("排序后的时间是: " + date2Str);
  27.         System.out.println("总共消耗时间约为：" + (date2.getTime() - date1.getTime()) + "ms");
  30.     }
  33.     /**
  34.      * 交换法
  35.      * @param arr
  36.      */
  37.     public static void shellSort1(int[] arr) {
  39.         int temp = 0;
  41.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  42.             for (int i = gap; i < arr.length; i++) {
  43.                 for (int j = i - gap; j >= 0; j -= gap) {
  44.                     if (arr[j] > arr[j + gap]) {
  45.                         temp = arr[j];
  46.                         arr[j] = arr[j + gap];
  47.                         arr[j + gap] = temp;
  48.                     }
  49.                 }
  50.             }
  51.         }
  53.     }
  55. }
  1. 移动法
  1. package shellsorting;
  3. import java.text.SimpleDateFormat;
  5. import java.util.Date;
  7. public class ShellSorting {
  9.     public static void main(String[] args) {
  11.         //int[] arr = {8,9,1,7,2,3,5,4,6,0};
  13.         int[] arr = new int[80000];
  14.         for (int i = 0; i < arr.length; i++) {
  15.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  16.         }
  18.         Date date1 = new Date();
  19.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  20.         String date1Str = simpleDateFormat.format(date1);
  21.         System.out.println("排序前的时间是: " + date1Str);
  23.         shellSort2(arr);
  25.         Date date2 = new Date();
  26.         String date2Str = simpleDateFormat.format(date2);
  27.         System.out.println("排序后的时间是: " + date2Str);
  29.         System.out.println("总共消耗时间约为：" + (date2.getTime() - date1.getTime()) + "ms");
  30.     }
  32.     /**
  33.      * 移动法
  34.      * @param arr
  35.      */
  36.     public static void shellSort2(int[] arr) {
  38.         //增量gap，并逐步的缩小增量
  39.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  40.             //从第gap个元算，逐步对其所在的组进行直接插入排序
  41.             for (int i = gap; i < arr.length; i++) {
  42.                 int j = i;
  43.                 int temp = arr[j];
  44.                 if (arr[j] < arr[j - gap]) {
  45.                     while (j - gap >= 0 && temp < arr[j - gap]) {
  46.                         //移动
  47.                         arr[j] = arr[j - gap];
  48.                         j -= gap;
  49.                     }
  50.                     //当退出while后，就给temp找到了最后的位置
  51.                     arr[j] = temp;
  52.                 }
  53.             }
  54.         }
  56.     }
  58. }
  1. 发现移动法的效率比交换法高

5. 快速排序(Quick Sort)

快速排序介绍

  1. 快速排序是对冒泡排序的一种改进。
  2. 快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码实现

  1. 基本实现
  1. package quicksort;
  3. import java.util.Arrays;
  5. public class QuickSort {
  7.     public static void main(String[] args) {
  8.         int[] arr = {-9,78,0,23,-567,70,1,5,78,454,45,45,-454,48};
  10.         System.out.println("排序前：" + Arrays.toString(arr));
  12.         quickSort(arr, 0, arr.length - 1);
  14.         System.out.println("排序后：" + Arrays.toString(arr));
  16.     }
  18.     public static void quickSort(int[] arr, int left, int right) {
  19.         int l = left;// 左下标
  20.         int r = right;// 右下标
  21.         // 中值
  22.         int pivot = arr[(left + right) / 2];
  23.         // 交换值
  24.         int temp = 0;
  26.         while (l < r) {// while的目的是让比pivot小的值放到它的左边，比pivot大的值放右边
  27.             // 在pivot的左边一直找，找到大于等于pivot的值，才退出
  28.             while (arr[l] < pivot) {
  29.                 l += 1;
  30.             }
  31.             // 在pivot的右边一直找，找到小于等于pivot的值，才退出
  32.             while (arr[r] > pivot) {
  33.                 r -= 1;
  34.             }
  35.             // l>=r说明pivot的左右的值，已经满足pivot的右边全都大于pivot，pivot的左边全都小于pivot
  36.             if (l >= r) {
  37.                 break;
  38.             }
  40.             // 交换
  41.             temp = arr[l];
  42.             arr[l] = arr[r];
  43.             arr[r] = temp;
  45.             // 如果交换完后，发现这个arr[l] == pivot值相等，则r--，前移
  46.             if (arr[l] == pivot) {
  47.                 r -= 1;
  48.             }
  49.             // 如果交换完后，发现这个arr[r] == pivot值相等，则l++，前移
  50.             if (arr[r] == pivot) {
  51.                 l += 1;
  52.             }
  53.         }
  55.         // 如果l == r。必须l++，r--，否则会出现栈溢出
  56.         if (l == r) {
  57.             l += 1;
  58.             r -= 1;
  59.         }
  60.         //向左递归
  61.         if (left < r) {
  62.             quickSort(arr, left, r);
  63.         }
  64.         //向右递归
  65.         if (right > l) {
  66.             quickSort(arr, l, right);
  67.         }
  70.     }
  72. }
  1. 运行速度测试
  1. package quicksort;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  6. public class QuickSort {
  8.     public static void main(String[] args) {
  10.         int[] arr = new int[80000];
  11.         for (int i = 0; i < arr.length; i++) {
  12.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  13.         }
  15.         Date date1 = new Date();
  16.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  17.         String date1Str = simpleDateFormat.format(date1);
  18.         System.out.println("排序前的时间是: " + date1Str);
  20.         quickSort(arr, 0, arr.length - 1);
  22.         Date date2 = new Date();
  23.         String date2Str = simpleDateFormat.format(date2);
  24.         System.out.println("排序后的时间是: " + date2Str);
  26.         System.out.println("总共消耗时间约为：" + (date2.getTime() - date1.getTime()) + "ms");
  28.     }
  30.     public static void quickSort(int[] arr, int left, int right) {
  31.         int l = left;// 左下标
  32.         int r = right;// 右下标
  33.         // 中值
  34.         int pivot = arr[(left + right) / 2];
  35.         // 交换值
  36.         int temp = 0;
  38.         while (l < r) {// while的目的是让比pivot小的值放到它的左边，比pivot大的值放右边
  39.             // 在pivot的左边一直找，找到大于等于pivot的值，才退出
  40.             while (arr[l] < pivot) {
  41.                 l += 1;
  42.             }
  43.             // 在pivot的右边一直找，找到小于等于pivot的值，才退出
  44.             while (arr[r] > pivot) {
  45.                 r -= 1;
  46.             }
  47.             // l>=r说明pivot的左右的值，已经满足pivot的右边全都大于pivot，pivot的左边全都小于pivot
  48.             if (l >= r) {
  49.                 break;
  50.             }
  52.             // 交换
  53.             temp = arr[l];
  54.             arr[l] = arr[r];
  55.             arr[r] = temp;
  57.             // 如果交换完后，发现这个arr[l] == pivot值相等，则r--，前移
  58.             if (arr[l] == pivot) {
  59.                 r -= 1;
  60.             }
  61.             // 如果交换完后，发现这个arr[r] == pivot值相等，则l++，前移
  62.             if (arr[r] == pivot) {
  63.                 l += 1;
  64.             }
  65.         }
  67.         // 如果l == r。必须l++，r--，否则会出现栈溢出
  68.         if (l == r) {
  69.             l += 1;
  70.             r -= 1;
  71.         }
  72.         //向左递归
  73.         if (left < r) {
  74.             quickSort(arr, left, r);
  75.         }
  76.         //向右递归
  77.         if (right > l) {
  78.             quickSort(arr, l, right);
  79.         }
  81.     }
  83. }

6. 归并排序(Merge Sort)

归并排序介绍

  1. 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分为治之）

代码实现

  1. 基本实现
  1. package mergesort;
  3. import java.util.Arrays;
  5. public class MergeSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {8,4,5,7,1,3,6,2};
  10.         int[] temp = new int[arr.length];
  12.         System.out.println("排序前：" + Arrays.toString(arr));
  14.         mergeSort(arr,0,arr.length - 1, temp);
  16.         System.out.println("排序前：" + Arrays.toString(arr));
  19.     }
  21.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  22.         if (left < right) {
  23.             int mid = (left + right) / 2;
  24.             //向左递归分解
  25.             mergeSort(arr, left, mid, temp);
  26.             //向右递归分解
  27.             mergeSort(arr, mid+1, right, temp);
  28.             //合并
  29.             merge(arr, left,mid,right,temp);
  30.         }
  31.     }
  33.     /**
  34.      *
  35.      * @param arr 待排序的数组
  36.      * @param left 左边有序序列的初始索引
  37.      * @param mid 中间索引
  38.      * @param right 右边索引
  39.      * @param temp 中转数组
  40.      */
  41.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
  43.         int i = left; // 初始化i，左边有序序列的初始索引
  44.         int j = mid + 1; //初始化j，表示右边有序序列的初始索引
  45.         int t = 0; // 指向temp数组的当前索引
  47.         //先把左右两边的数据按规则填充到temp数组
  48.         //直到左右两边有序序列有一边处理完毕
  49.         while (i <= mid && j <= right) {
  50.             //左边小于等于右边
  51.             if (arr[i] <= arr[j]) {
  52.                 temp[t] = arr[i];
  53.                 t++;
  54.                 i++;
  55.             } else {
  56.                 temp[t] = arr[j];
  57.                 t++;
  58.                 j++;
  59.             }
  60.         }
  62.         //把有剩余数据的一边的数据依次全部填充到temp中，
  63.         //左边未完
  64.         while ( i <= mid) {
  65.             temp[t] = arr[i];
  66.             t++;
  67.             i++;
  68.         }
  69.         //右边未完
  70.         while (j <= right) {
  71.             temp[t] = arr[j];
  72.             t++;
  73.             j++;
  74.         }
  76.         //将temp数组中的数据拷贝到arr
  77.         t = 0;
  78.         int tempLeft = left;
  79.         while (tempLeft <= right) {
  80.             arr[tempLeft] = temp[t];
  81.             t++;
  82.             tempLeft++;
  83.         }
  84.     }
  86. }
  1. 运行速度测试
  1. package mergesort;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Arrays;
  5. import java.util.Date;
  7. public class MergeSort {
  9.     public static void main(String[] args) {
  11.         int[] arr = new int[80000];
  12.         for (int i = 0; i < arr.length; i++) {
  13.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  14.         }
  15.         int[] temp = new int[arr.length];
  17.         Date date1 = new Date();
  18.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  19.         String date1Str = simpleDateFormat.format(date1);
  20.         System.out.println("排序前的时间是: " + date1Str);
  22.         mergeSort(arr,0,arr.length - 1, temp);
  24.         Date date2 = new Date();
  25.         String date2Str = simpleDateFormat.format(date2);
  26.         System.out.println("排序后的时间是: " + date2Str);
  28.         System.out.println("总共消耗时间约为：" + (date2.getTime() - date1.getTime()) + "ms");
  30.     }
  32.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  33.         if (left < right) {
  34.             int mid = (left + right) / 2;
  35.             //向左递归分解
  36.             mergeSort(arr, left, mid, temp);
  37.             //向右递归分解
  38.             mergeSort(arr, mid+1, right, temp);
  39.             //合并
  40.             merge(arr, left,mid,right,temp);
  41.         }
  42.     }
  44.     /**
  45.      *
  46.      * @param arr 待排序的数组
  47.      * @param left 左边有序序列的初始索引
  48.      * @param mid 中间索引
  49.      * @param right 右边索引
  50.      * @param temp 中转数组
  51.      */
  52.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
  54.         int i = left; // 初始化i，左边有序序列的初始索引
  55.         int j = mid + 1; //初始化j，表示右边有序序列的初始索引
  56.         int t = 0; // 指向temp数组的当前索引
  58.         //先把左右两边的数据按规则填充到temp数组
  59.         //直到左右两边有序序列有一边处理完毕
  60.         while (i <= mid && j <= right) {
  61.             //左边小于等于右边
  62.             if (arr[i] <= arr[j]) {
  63.                 temp[t] = arr[i];
  64.                 t++;
  65.                 i++;
  66.             } else {
  67.                 temp[t] = arr[j];
  68.                 t++;
  69.                 j++;
  70.             }
  71.         }
  73.         //把有剩余数据的一边的数据依次全部填充到temp中，
  74.         //左边未完
  75.         while ( i <= mid) {
  76.             temp[t] = arr[i];
  77.             t++;
  78.             i++;
  79.         }
  80.         //右边未完
  81.         while (j <= right) {
  82.             temp[t] = arr[j];
  83.             t++;
  84.             j++;
  85.         }
  87.         //将temp数组中的数据拷贝到arr
  88.         t = 0;
  89.         int tempLeft = left;
  90.         while (tempLeft <= right) {
  91.             arr[tempLeft] = temp[t];
  92.             t++;
  93.             tempLeft++;
  94.         }
  95.     }
  97. }

7.基数排序(Radix Sort)

基数排序介绍

  1. 基数排序属于“分配式排序”(Distribution Sort)，又称“桶子法”(Bucket Sort)，它是通过键值的各个位的值，将要排序的元素分配至”桶“中，达到排序的作用
  2. 基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法
  3. 基数排序是“桶排序”的扩展，速度很快
  4. 技术排序是1887年赫尔曼·何乐礼发明的，将证书按位数切割成不同的数字，然后按每个位数分别比较
  5. 基数排序的基本思想是：将所有待比较数值同意为同样长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成了一个有序序列
  6. 基数排序是经典的空间换时间的方式，占内存很大，当对海量数据排序时，容易造成OutOfMemoryError
  7. 有负数的数组，我们不用基数排序来进行排序，如果需要支持负数，参考https://code.i-harness.com/zh-CN/q/e98fa9

代码实现

  1. 基本实现
  1. package radixsort;
  3. import java.util.Arrays;
  5. public class RadixSort {
  7.     public static void main(String[] args) {
  9.         int[] arr = {53,3,542,748,14,214};
  11.         System.out.println("排序前：" + Arrays.toString(arr));
  13.         radixSort(arr);
  15.         System.out.println("排序前：" + Arrays.toString(arr));
  17.     }
  19.     public static void radixSort(int[] arr) {
  21.         //定义10个桶
  22.         int[][] bucket = new int[10][arr.length];
  24.         //为了记录每个桶中实际存放了多少个数据，定义一个一维数组，记录各个桶每次放入的数据个数
  25.         int[] bucketElementCounts = new int[10];
  27.         //得到数组中最大数据的位数
  28.         int max = arr[0];// 假设是第一个
  29.         for (int i = 1; i < arr.length; i++) {
  30.             if (arr[i] > max) {
  31.                 max = arr[i];
  32.             }
  33.         }
  34.         int maxLength = (max + "").length();
  36.         for (int i = 0; i < maxLength; i++) {
  37.             for (int j = 0; j < arr.length; j++) {
  38.                 //取出每个元素的个位数字
  39.                 int digitOfElement = arr[j] / ((int)Math.pow(10, i)) % 10;
  40.                 //放在对应的桶中
  41.                 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  42.                 bucketElementCounts[digitOfElement]++;
  43.             }
  45.             //将桶中的数据放会arr中
  46.             int index = 0;
  47.             for (int k = 0; k < bucket.length; k++) {
  48.                 //如果桶中存在数据，才放回原数组
  49.                 if (bucketElementCounts[k] != 0) {
  50.                     //遍历第k个桶
  51.                     for (int l = 0; l < bucketElementCounts[k]; l++) {
  52.                         //取出数据，将数据放回arr
  53.                         arr[index] = bucket[k][l];
  54.                         index++;
  55.                     }
  56.                 }
  57.                 //需要将bucketElementCounts[k]重新置为0！！！
  58.                 bucketElementCounts[k] = 0;
  59.             }
  60.         }
  62.     }
  64. }
  1. 运行速度测试
  1. package radixsort;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  6. public class RadixSort {
  8.     public static void main(String[] args) {
  10.         int[] arr = new int[80000];
  11.         for (int i = 0; i < arr.length; i++) {
  12.             arr[i] = (int)(Math.random() * 8000000);//产生一个0-8000000的数
  13.         }
  15.         Date date1 = new Date();
  16.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd-HH:mm:ss");
  17.         String date1Str = simpleDateFormat.format(date1);
  18.         System.out.println("排序前的时间是: " + date1Str);
  20.         radixSort(arr);
  22.         Date date2 = new Date();
  23.         String date2Str = simpleDateFormat.format(date2);
  24.         System.out.println("排序后的时间是: " + date2Str);
  26.         System.out.println("总共消耗时间约为：" + (date2.getTime() - date1.getTime()) + "ms");
  28.     }
  30.     public static void radixSort(int[] arr) {
  32.         //定义10个桶
  33.         int[][] bucket = new int[10][arr.length];
  35.         //为了记录每个桶中实际存放了多少个数据，定义一个一维数组，记录各个桶每次放入的数据个数
  36.         int[] bucketElementCounts = new int[10];
  38.         //得到数组中最大数据的位数
  39.         int max = arr[0];// 假设是第一个
  40.         for (int i = 1; i < arr.length; i++) {
  41.             if (arr[i] > max) {
  42.                 max = arr[i];
  43.             }
  44.         }
  45.         int maxLength = (max + "").length();
  47.         for (int i = 0; i < maxLength; i++) {
  48.             for (int j = 0; j < arr.length; j++) {
  49.                 //取出每个元素的个位数字
  50.                 int digitOfElement = arr[j] / ((int)Math.pow(10, i)) % 10;
  51.                 //放在对应的桶中
  52.                 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  53.                 bucketElementCounts[digitOfElement]++;
  54.             }
  56.             //将桶中的数据放会arr中
  57.             int index = 0;
  58.             for (int k = 0; k < bucket.length; k++) {
  59.                 //如果桶中存在数据，才放回原数组
  60.                 if (bucketElementCounts[k] != 0) {
  61.                     //遍历第k个桶
  62.                     for (int l = 0; l < bucketElementCounts[k]; l++) {
  63.                         //取出数据，将数据放回arr
  64.                         arr[index] = bucket[k][l];
  65.                         index++;
  66.                     }
  67.                 }
  68.                 //需要将bucketElementCounts[k]重新置为0！！！
  69.                 bucketElementCounts[k] = 0;
  70.             }
  71.         }
  73.     }
  75. }

查找

介绍

在java中，我们常用的查找有4种

  • 顺序（线性）查找
  • 二分查找/折半查找
  • 插值查找
  • 斐波那契查找

1. 线性查找(Linear Search)

线性查找介绍

  1. 查找的序列可也是有序的，也可以是无序的
  2. 线性查找思路：线性查找是逐一比对，发现有相同值，就返回下标

代码实现

  1. package linearsearch;
  3. import java.util.Arrays;
  5. public class LinearSearch {
  7.     public static void main(String[] args) {
  9.         int[] arr = {1,9,11,-1,34,89}; //可有序，可无序
  10.         int index, value;
  12.         System.out.println("arr = " + Arrays.toString(arr));
  14.         value = 11;
  15.         index = linearSearch(arr, value);
  17.         if (index == -1) {
  18.             System.out.println("没有找到" + value);
  19.         } else {
  20.             System.out.println("下标为" + index);
  21.         }
  23.     }
  25.     /**
  26.      * 这个方法是找到一个满足条件就返回
  27.      * @param arr 查询数组
  28.      * @param value 查询值
  29.      * @return 查询值在查询数组中的索引
  30.      */
  31.     public static int linearSearch(int[] arr, int value) {
  32.         //线性查找是逐一比对，发现有相同值，就返回下标
  33.         for (int i = 0; i < arr.length; i++) {
  34.             if (arr[i] == value) {
  35.                 return i;
  36.             }
  37.         }
  38.         return -1;
  39.     }
  41. }

2. 二分查找(Binary Search)

二分查找介绍

  1. 查找的序列必须是有序的，要查找需要将序列进行排序
  2. 发现有相同值，就返回下标
  3. 存在两种方法，递归和非递归
  4. 二分查找的思路分析(假设arr数组是升序)：
    • 首先确定该数组的中间的下标，mid = (left + right) / 2
    • 然后让需要查找的数findValue和arr[mid]作比较
    • 若indValue>arr[mid]，则indValue在arr[mid]的右边，反之则在左边，若indValue==arr[mid]，则返回mid。进行递归操作
    • 考虑到找不到时，当left>right就会退出递归

代码实现

  1. 基本实现
  1. package binarysearch;
  3. import java.util.Arrays;
  5. public class BinarySearch {
  7.     public static void main(String[] args) {
  8.         // 使用二分查找的前提，该数组是有序的
  9.         int[] arr = {1,8,10,89,1000,1234};
  10.         int index, value;
  12.         System.out.println("arr = " + Arrays.toString(arr));
  14. //        value = 9;
  15.         value = 10;
  16.         index = binarySearch(arr, 0, arr.length - 1, value);
  18.         if (index == -1) {
  19.             System.out.println("没有找到" + value);
  20.         } else {
  21.             System.out.println("下标为" + index);
  22.         }
  23.     }
  25.     /**
  26.      *
  27.      * @param arr 数组
  28.      * @param left 左边的索引
  29.      * @param right 右边的索引
  30.      * @param value 查找的值
  31.      * @return 如果找到就返回该值在数组里的索引，没找到就返回-1
  32.      */
  33.     public static int binarySearch(int[] arr, int left, int right, int value) {
  35.         // 没找到的退出递归条件
  36.         if (left > right) {
  37.             return -1;
  38.         }
  40.         int mid = (left + right) / 2;
  41.         int midValue = arr[mid];
  43.         if (value < midValue) {// 向左递归
  44.             return binarySearch(arr, left, mid - 1, value);
  45.         } else if (value > midValue) {// 向右递归
  46.             return binarySearch(arr, mid + 1, right, value);
  47.         } else {// 找到了
  48.             return mid;
  49.         }
  51.     }
  53. }
  1. 当一个有序数组中存在多个相同值时，将所有数值都查找到
  1. package binarysearch;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  6. public class BinarySearch {
  8.     public static void main(String[] args) {
  9.         // 使用二分查找的前提，该数组是有序的
  10.         int[] arr = {1,8,10,89,1000,1000,1000,1000,1234};
  11.         int index, value;
  13.         System.out.println("arr = " + Arrays.toString(arr));
  15. //        value = 9;
  16.         value = 1000;
  18.         ArrayList<Integer> indexes = binarySearch2(arr, 0, arr.length - 1, value);
  20.         if (indexes.size() == 0) {
  21.             System.out.println("没有找到" + value);
  22.         } else {
  23.             System.out.println(value + "下标为" + indexes);
  24.         }
  26.     }
  28.     //当一个有序数组中存在多个相同值时，将所有数值都查找到，返回所有下标
  29.     /**
  30.      * 在原先二分法进行优化，在找到匹配数值时，不要一找到就返回
  31.      * 向mid索引值的左边扫描，将所有满足等于查找值的下标加入到ArrayList，右边同理
  32.      * @param arr 数组
  33.      * @param left 左边的索引
  34.      * @param right 右边的索引
  35.      * @param value 查找的值
  36.      * @return
  37.      */
  38.     public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int value) {
  40.         // 没找到的退出递归条件
  41.         if (left > right) {
  42.             return new ArrayList<Integer>();
  43.         }
  45.         int mid = (left + right) / 2;
  46.         int midValue = arr[mid];
  48.         if (value < midValue) {// 向左递归
  49.             return binarySearch2(arr, left, mid - 1, value);
  50.         } else if (value > midValue) {// 向右递归
  51.             return binarySearch2(arr, mid + 1, right, value);
  52.         } else {// 找到了
  53.             ArrayList<Integer> list = new ArrayList<>();
  54.             //向左边扫描
  55.             int temp = mid - 1;
  56.             while (true) {
  57.                 if (temp < 0 || arr[temp] != value) {
  58.                     break;
  59.                 }
  60.                 list.add(temp);
  61.                 temp--;
  62.             }
  63.             list.add(mid);
  64.             //向右边扫描
  65.             temp = mid + 1;
  66.             while (true) {
  67.                 if (temp > arr.length - 1 || arr[temp] != value) {
  68.                     break;
  69.                 }
  70.                 list.add(temp);
  71.                 temp++;
  72.             }
  73.             return list;
  74.         }
  76.     }
  78. }

3. 插值查找(Interpolation Search)

插值查找介绍

  1. 插值查找原理如下：
    • 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid开始查找
    • 将折半查找中的求mid索引的公式，low表示左边索引left，high表示右边索引right算法 - 图1%0A#card=math&code=mid%3D%5Cfrac%7Blow%2Bhigh%7D%7B2%7D%3Dlow%2B%5Cfrac%7B1%7D%7B2%7D%28high-low%29%0A)

改成下列式子(key代表要查找的值)，自适应算法 - 图2%0A#card=math&code=mid%3Dlow%2B%5Cfrac%7Bkey-a%5Blow%5D%7D%7Ba%5Bhigh%5D-a%5Blow%5D%7D%28high-low%29%0A)

  • 举例说明插值查找算法1-100的数组，假如我们要查找的值为1
    • 使用二分查找，我们要进行多次递归，才能找到1
    • 使用插值查找，第一次mid=0+((1-1)/(100-1))*(99-0)=0，而a[mid]=a[0]=1，一次就直接找到了1
      1. 插值查找注意事项
  • 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
  • 关键字分布不均匀的情况下，该方法不一定比折半查找好

代码实现

  1. 基本实现
  1. package interpolationsearch;
  3. import java.util.Arrays;
  5. public class InterpolationSearch {
  7.     public static void main(String[] args) {
  8.         //初始化数组
  9.         int[] arr = new int[100];
  10.         for (int i = 0; i < 100; i++) {
  11.             arr[i] = i + 1;
  12.         }
  13.         int index, value;
  15.         System.out.println("arr = " + Arrays.toString(arr));
  17.         value = 2;
  19.         index = interpolationSearch(arr, 0, arr.length - 1, value);
  21.         if (index == -1) {
  22.             System.out.println("没有找到" + value);
  23.         } else {
  24.             System.out.println("下标为" + index);
  25.         }
  27.     }
  29.     /**
  30.      * 插值查找算法，也要求数组是有序的
  31.      * @param arr 数组
  32.      * @param left 左边索引
  33.      * @param right 右边索引
  34.      * @param value 查找值
  35.      * @return 返回查找值在arr数组中的下标，若没找到，则返回-1
  36.      */
  37.     public static int interpolationSearch(int[] arr, int left, int right, int value) {
  38.         //注意：value < arr[0] || value > arr[arr.length - 1 必须要，否则可能会越界
  39.         if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
  40.             return -1;
  41.         }
  43.         // 求出mid
  44.         int mid = left + (right - left) * ((value - arr[left]) / (arr[right] - arr[left]));
  45.         int midValue = arr[mid];
  47.         if (value < midValue) {// 左递归
  48.             return interpolationSearch(arr, left, mid - 1, value);
  49.         } else if (value > midValue) {// 右递归
  50.             return interpolationSearch(arr, mid + 1, right, value);
  51.         } else {
  52.             return mid;
  53.         }
  55.     }
  57. }

4. 斐波那契查找(Fibonacci Search)

斐波那契查找介绍

  1. 斐波那契又称为黄金分割法
  2. 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意想不到的效果。
  3. 斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618
  4. 斐波那契（黄金分割法）原理：
    • 斐波那契原理与二分查找、插值查找相似，仅仅改变了中间结点(mid)的位置，mid不再是中间或插值得到的，而是位于黄金分割点附近，即mid=low+F(k-1)-1，F代表斐波那契数列
    • 对F(k-1)-1的理解：
      • 由斐波那契数列F[k]=F[k-1]+F[k-2]的性质，可以得到(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如下图所示。从而中间位置为mid=low+F(k-1)-1

斐波那契查找-1.png

  1.   - 类似的，每一子段也可以用相同的方式分割
  2.   - 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置)，都赋为n位置的值即可。
  1. while(n > fib(k) - 1)
  2.     k++;

代码实现

  1. 基本实现
  1. package fibonaccisearch;
  3. import java.util.Arrays;
  5. public class FibonacciSearch {
  7.     private final static int MAXSIZE = 20;
  9.     public static void main(String[] args) {
  11.         int[] arr = {1,8,10,89,100,1234};
  12.         int index, value;
  14.         value = 8;
  16.         index = fibonacciSearch(arr, value);
  18.         if (index == -1) {
  19.             System.out.println("没有找到" + value);
  20.         } else {
  21.             System.out.println("下标为" + index);
  22.         }
  24.     }
  26.     //因为会使用到斐波那契数列，因此我们先获取到斐波那契数列
  27.     //用非递归的方式得到斐波那契数列
  28.     public static int[] fib() {
  29.         int[] f = new int[MAXSIZE];
  30.         f[0] = 1;
  31.         f[1] = 1;
  32.         for (int i = 2; i < MAXSIZE; i++) {
  33.             f[i] = f[i - 1] + f[i - 2];
  34.         }
  35.         return f;
  36.     }
  38.     //编写斐波那契查找算法
  39.     //使用非递归的方式编写算法
  40.     /**
  41.      *
  42.      * @param arr 数组
  43.      * @param value 查找值
  44.      * @return 找到就返回查找值得下标，若没找到就返回-1
  45.      */
  46.     public static int fibonacciSearch(int[] arr, int value) {
  47.         int low = 0;
  48.         int high = arr.length - 1;
  49.         int k = 0; //表示斐波那契分割数值的下标
  50.         int mid = 0; //存放mid的值
  51.         int[] f = fib();//获取斐波那契数列
  52.         //获取斐波那契分割数值的下标
  53.         while (high > f[k] - 1) {
  54.             k++;
  55.         }
  56.         //因为f[k]可能大于数组arr的长度，因此需要使用Arrays，构造一个新的数组，并指向arr
  57.         //不足的部分会使用0填充
  58.         int[] temp = Arrays.copyOf(arr, f[k]);
  59.         //填充值
  60.         for (int i = high + 1; i < temp.length; i++) {
  61.             temp[i] = arr[high];
  62.         }
  63.         //使用while循环处理，来找到value
  64.         while (low <= high) {
  65.             mid = low + f[k-1]-1;
  66.             if (value < temp[mid]) {// 向数组的前部分查找(左边)
  67.                 high = mid - 1;
  68.                 //为什么是k--
  69.                 //1. 全部元素 = 前面的元素 + 后边的元素
  70.                 //2. f[k] = f[k-1] + f[k-2]
  71.                 //3. 因为前面有f[k-1]个元素，所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
  72.                 //4. 即在f[k-1]的前面继续查找，所以是k--
  73.                 //5. 即下次循环mid =  low + f[k-1-1]-1;
  74.                 k--;
  75.             } else if (value > temp[mid]) {// 向数组的后部分查找(右边)
  76.                 low = mid + 1;
  77.                 //为什么是k-2
  78.                 //1. 全部元素 = 前面的元素 + 后边的元素
  79.                 //2. f[k] = f[k-1] + f[k-2]
  80.                 //3. 因为后面有f[k-2]个元素，所以可以继续拆分f[k-2] = f[k-3] + f[k-4]
  81.                 //4. 即在f[k-2]的前面继续查找，所以是k-=2
  82.                 //5. 即下次循环mid =  low + f[k-1-2]-1;
  83.                 k -=2;
  84.             } else { //找到
  85.                 if (mid <= high) {
  86.                     return mid;
  87.                 } else {
  88.                     return high;
  89.                 }
  90.             }
  91.         }
  92.         return -1;
  93.     }
  95. }