Java常用算法

常用的算法思想主要包含以下几个方面：

1.分治法：

分治法的主要思想就是将一个复杂的问题分解成规模较小的相同问题，最终分割成的小问题可以很方便的求解，原问题的解就是每个小问题的合并。

• 分治法思想解决的经典问题：

  • 二分查找

    
    binarySearch.png
    

    二分查找也称之为折半算法，是在一个有序的数组中查找某一特定的元素的算法，并且每一次查找都可以将搜索范围缩小一般。

            // 二分搜索法，查找有序数组中某个数的下标。
            public static int binarySearch(int[] searchArray, int searchData) {
                int start = 0;
                int end = searchArray.length - 1;
                int mid;
                while (start <= end) {
                    mid = (start + end) / 2;
                    if (searchData < searchArray[mid]) {
                        end = mid - 1;
                    } else if (searchData > searchArray[mid]) {
                        start = mid + 1;
                    } else {
                        return mid;
                    }
                }
                return -1;
            }   
    
    

  • 快速排序
    1.基本思想： 从无序数列（R[low...high]）中选取一个基准数（pivot，一般选择low），从右侧开始扫描如果找到比pivot小的数，就将R[start] = R[end]（将此高位的数据保存低位）并且将start++,然后从左侧扫描如果找到比pivot大的数，就将R[end] = R[start],并且将end--；如此反复执行，当start= end时，结束扫描，并且将R[start] = pivot。

    2.基本思想图解：
    

    quickSort_1.png
    ①、初始化时，选取基准数 int pivot = R[0]=72,start= 0,end= 9。
    从右侧开始扫描，当end= 8时，R[8] < pivot，然后将R[start] = R[8]，start++，再从左侧start处进行扫描，当start = 3是，R[3] > pivot,然后将R[end] = R[3]，end--。得到的结果如图｛quickSort_2.png｝。
    quickSort_2.png
    ②、此时，start = 3,end = 7,pivot = 72，再重复上面的扫描步骤，先从右侧扫描，再从左侧扫描。当end = 5时，R[5] < pivot，然后将R[start] = R[5],start++，之后扫描左侧并不会发现比pivot大的数值了。
    quickSort_3.png
    ③、最终扫描得到：start = end = 5，因此扫描结束了，再将R[start] = pivot。
    经过上述一轮扫描之后发现，pivot所处的位置的左边都是比pivot小的数值，右边都是它大的数值；如此就相当于分化了两个相似的子问题，只需要递归执行左右两边的遍历，即可将整个问题解决。
    代码实现：

          public static void quickSort(int[] array, int start, int end) {
                   if (start < end) {
                        int pivot = array[start];
                        while (start < end) {
                              // 1.从左侧进行扫描
                              while (start < end && array[end] >= pivot) end--;
                              // 扫描到比pivot小的数值
                              if (start < end) {
                                      array[start] = array[end];
                                      start++;
                              }
    
                              // 2.从右侧进行扫描
                              while (start < end && array[start] <= pivot) start++;
                              // 扫描到比pivot大的数值
                               if (start < end) {
                                      array[end] = array[start];
                                      end--;
                               }
                    }
                   // 3.一轮扫描结束，将pivot归位
                   array[start] = pivot;
    
                  // 4.递归调用
                 quickSort(array, 0, start - 1);// 左侧递归
                 quickSort(array, start + 1, end);// 右侧递归
               }
         }
    
    

2.穷举法

• 基本思想:穷举法就是针对问题穷举出每一种可能的结果，并且对每一个结果进行判断，从而得出正确的答案。

• 穷举法的使用场景：

  • 找出[1,100]中之间的素数？

    首先，我们会将[1,100]的数全部都一一列举出来，然后再将这个列举出来的数进行判断。

      // 判断是否为素数
      private boolean isPrime(int num){
          boolean isPrime = true;
          for(int i = 2;i < num;i++){
              if(0 == num % i){
                  isPrime = false;
              }
          }
          return isPrime;
      }
    
      // 列出某个区间内所有的素数
      public void listPrime(int start,int end){
          for(int i = start;i <= end;i++){
              if(isPrime(i)){
                  Log.d("TAG",i+" ");
              }
          }
      }