一. 二分查找

前提：数组中的数据必须是按照大小顺序排列。数组的二分查找步骤：

  • 定义两个变量，表示要查找的范围。默认min = 0，max = 最大索引；
  • 循环查找，但是min <= max；
  • 计算出mid的值；
  • 判断mid位置的元素是否为要查找的元素，如果是，直接返回对应的索引；
  • 如果要查找的值在mid的左边，那么min值不变，max = mid - 1，继续下一次循环查找；
  • 如果要查找的值在mid的右边，那么max值不变，min = mid + 1，继续下一次循环查找；
  • 当min > max时，表示要查找的元素在数组中不存在，返回-1。
  1. public class BinarySearchUtil {
  2.     public static int BinarySearch(int[] arr,int num){
  3.         //定义查找范围，备注：索引。
  4.         int min = 0;
  5.         int max = arr.length - 1;
  6.         //循环查找min <= max
  7.         while (min <= max){
  8.             //计算出中间位置的mid
  9.             int mid = (min + max) / 2;
  10.             if(arr[mid] < num){
  11.                 //表示要查的数在mid的右边
  12.                 min = mid + 1;
  13.             }else if(arr[mid] > num){
  14.                 max = mid - 1;
  15.             }else {
  16.                 return mid;
  17.             }
  18.         }
  19.         return -1;
  20.     }
  21. }

二. 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

  1. public static void main(String[] args) {
  2.     int[] arr = new int[]{0,1,6,9,2,5,3,7,4,8};
  3.     //调用快速排序算法
  4.     quick(arr,0,arr.length-1);
  5.     //打印排序的后结果，查看是否正确
  6.     System.out.println(Arrays.toString(arr));
  7. }
  8. public static void quick(int[] arr,int start,int end){
  9.     //如果开始位置和结束位置重合，实际上数组里面就是一个数字，就没有排序的意义，所以开始位置一定要比结束位置小，而且不能相等。
  10.     if(start < end){
  11.         //设定标准数，也就是快速排序的过程中，和谁进行比较，通常用第一个数字即可
  12.         //注意这里用的是arr[start],按说在第一次的时候是0，应该写成arr[start],但是不可以，因为快速排序是一个递归的操作，第二次进来的时候，就不是arr[0]了
  13.         int stand = arr[start];
  14.         /**
  15.          *  开始找开始位置和结束位置
  16.          *  我们知道快速排序其实就是有一个开始位置和一个结束位置，当开始位置比选定的标准数字大的时候，
  17.          *  就会替换掉结束位置的数字，这个时候结束位置的下表开始向前移动，然后如果结束位置的数字比标准数字，
  18.          *  则替换开始位置的数字，在循环的过程中如果开始位置/结束位置的数字 不比标准数字大或者小，
  19.          *  这个时候开始位置和结束位置就会向后/向前移动
  20.          */
  21.         //开始位置
  22.         int low = start;
  23.         //结束位置
  24.         int high = end;
  25.         while (low<high){
  26.             //这个时候我们已经找定了开始位置和结束位置，第一次是要拿高位和低位进行比较,如果高位比标准数字大，则高位则向前移动一位
  27.             while (low < high && arr[high] > stand){
  28.                 high--;
  29.             }
  30.             //当然了并不是所有高位数字都比低位大，如果比低位要小，则这个数字要覆盖低位的数字
  31.             arr[low] = arr[high];
  32.             //然后这个时候低位开始移动，如果低位比标准数字小，则低位的下标向后移动一位
  33.             while (low < high && arr[low] < stand){
  34.                 low++;
  35.             }
  36.             //当然了并不是所有时候低位都比标准数字要小，如果比标准数字大的话，这个时候就要替换掉高位的数字
  37.             arr[high] = arr[low];
  38.         }
  39.         //经过上面的一番折腾，这个时候就会出现一个情况，低位和高位相同，那么这个位置就用标准数字去替换
  40.         //这里low和high实际上是相同的数字，所以写哪个都无所谓
  41.         arr[low] = stand; //然后第一轮排序完毕，我们就会发现以标准数字为分界线，我们有两个学列了，这个时候，我们就调用递归来
  42.         //分别对两个序列进行排序
  43.         //先出来低位的递归,最后的位置实际上有可能是高位，有可能是低位，既然上面写的是低位，这里就写低位就好了
  44.         quick(arr,start,low); //然后出来高位的数字
  45.         quick(arr,low+1,end);
  46.     }
  47. }

本工具类直接可以使用哦～

三. 冒泡排序

冒泡排序原理：

  • 相邻两元素两两比较，大的放右边，小的放左边，找到最大值；
  • 以后的每次只需要在剩余的数字里面找到最大值直到剩余最后一个数。
    1. public class BubbleSortUtil {
    2.   public static int[] BubbleSort(int[] arr){
    3.       //控制循环的次数，比数组长度少一次，每次循环确定一次最大值
    4.      for (int i = 0;i < arr.length -1;i++){
    5.          //内部循环是进行比较的，-i是因为每循环完一次，确定一个最大值，进行比较的长度就会少一个。
    6.          for (int j = 0;j < arr.length - 1 - i;j++){
    7.              if (arr[j] - arr[j+1] > 0){
    8.                  //数据替换
    9.                  int temp = arr[j];
    10.                  arr[j] = arr[j+1];
    11.                  arr[j+1] = temp;
    12.              }
    13.          }
    14.      }
    15.       return arr;
    16.   }
    17. }
    本工具类可直接使用。