基础算法

发表于 | 分类于


基础算法，算法有时候好玩，有时候不好玩。看得懂和写得出差距很大很大。

写在前面

文章算法正确性均未验证，只是谈谈思路。

常用算法

分治

  • 将大问题分解为小问题
  • 合并小问题的解即为大问题的解，小问题之间相互独立。
    在大数据中，基于MR思想的分布式计算框架，比如MapReduce和Spark。都是典型的分治法的利用。
    数据分区，分区内的管道式计算。属于“分”，分区内的数据互不干扰，相互独立。
    分区结果多路归并，比如Reduce操作。得到最优解。

动态规划

贪心

回溯

分支限界

快速排序算法

  • 算法思想：分治法
  • 算法思路：
    • 从数组取一个数作为基准元（固定基准元、随机基准元、三数取中，目的是使分隔成的子数组长度尽可能相等）
    • 将数组分割成左右2个子数组，左数组小于基准元，右数组大于基准元。并返回新的基准元下标。（注意边界条件是low<high）
    • 对左右数组分别递归调用，直到low<high
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      //定义分区函数，将数组分为左右数组并返回大小分界处的元素下标。
      public int Partition(int[] arr,int low,int high){
          //取low下标元素作为基准元
          int keyNum = arr[low];
          int i = low,j = high;
          while(i<j){
            while(arr[i]>keyNum&&i<j){//找到左边大于基准元的元素下标
              i++;
            }
            while(arr[j]<keyNum&&i<j){//找到右边小于基准元的元素下标
              j--;
            }
            if(i<j){//交换i，j元素
              swap(arr,i,j);
            }
          }
          /**
           * 循环结束时，左数组小于基准元，右数组大于基准元，
           * 但是基准元还是位于low处（等于被忽略），所以应将基准元放回中间位置
           **/
           swap(arr,low,i);
           return i; //此时的i就是i==j(low==high)的时候
      }
      public void qsort(int[] arr,int low,int high){
        if(low<high){
          int division  = Partition(arr,low,high); //得到左右分区边界下标
          qsort(arr,low,division-1); //division可以认为有序，递归时应跳过division项
          qsort(arr,division+1,high);
        }
      }
      `