算法（Algorithm）整理回顾

算法复杂度

时间复杂度

大O复杂度表示法
T(n)	代码执行时间
n	数据规模，当n无限大时，低阶、常量、系统都可以忽略
f(n)	每行代码执行次数总和
O	代码的执行时间与f(n)表达式成正比

例如下述代码，T(n)=O(n*n)

int sum(int n){
  int s=0;//1
  int i=1;//1
  int j=1;//1
  for(;i<=n;i++){//n
    j=1;//n
    for(;j<=n;j++){//n*n
      s=s+i+j;//n*n
    }
  } 
  return s;//1
}

常见算法复杂度

O(1)

不是只执行了一行代码，只要代码的执行不随着数据规模(n)的增加而增加，就是常量级

在实际应用中，通常使用冗余字段存储来将O(n)变成O(1)，比如Redis中有很多这样的操作用来提升访问性能：比如:SDS、字典、跳跃表等
O(logn)、O(nlogn)：

比如快速排序、归并排序的时间复杂度都是O(nlogn)
O(n)

很多线性表的操作都是O(n)，这也是最常见的一个时间复杂度，比如：数组的插入删除、链表的遍历等
O(m+n)

m和n是代码的两个数据规模，而且不能确定谁更大，此时代码的复杂度为两段时间复杂度之和。

空间复杂度

由于现在硬件相对比较便宜，所以在开发中常常会利用空间来换时间，比如缓存技术典型的数据结构中空间换时间是：跳跃表
在实际开发中我们也更关注代码的时间复杂度，而用于执行效率的提升

常见算法

递归

概念：一种循环，而且在循环中执行的就是调用自己递归调用将每次返回的结果存在栈帧中，其内容三要素包括递归结束条件、函数的功能、函数的等价关系式，即递归公式。
应用：斐波那契数列（普通递归解法为O(2^n) ）
优点：代码简单
缺点：1.占用空间较大；2.如果递归太深，可能会发生栈溢出；3.可能会有重复计算（通过备忘录或递归的方式去优化-动态规划）

二分查找

概念：二分查找（Binary Search）算法，也叫折半查找算法，是针对有序数据集合的查找算法。
经典题型：一个有序的数组中查找某个数字是否存在；一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数；快速定位出一个 IP 地址的归属地
优点：1.速度快，时间复杂度为O(logn)，每次都能排除剩余元素中一半的元素，包含目标元素的有效范围就收缩得很快；2.不占空间；3.不开辟新空间
缺点：必须是有序的数组（数据量太小没有意义，但数据量也不能太大，因为数组要占用连续的空间）

排序

冒泡排序

时间复杂度：O(n^2)
实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = new int[]{3, 8, 11, 13, 9, 2, 1, 4, 16, 3};
        bubbleSort(array, array.length);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

    static void bubbleSort(int[] array, int length) {
        if (length == 0) {
            return;
        } else {
            for (int i = 0; i < length - 1; i++) {
                if (array[i] > array[i + 1]) {
                    int tmp = array[i + 1];
                    array[i + 1] = array[i];
                    array[i] = tmp;
                }
            }
        }
        bubbleSort(array, --length);
    }
}

快速排序

时间复杂度：O(nlogn)
实现

/**
 * （双指针）快排：选定基准，分治比较
 * 时间复杂度：最坏情况 N^2 ,平均 NlogN
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] array = new int[]{3, 8, 11, 13, 9, 2, 1, 4, 16, 3};
      int[] array = new int[]{3,3,4,3};
        quickSort(array, 0, 1, array.length - 1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    static void quickSort(int[] array, int pivotIndex, int left, int right) {
        if (left > right) {
            return;
        }
        int pivot = array[pivotIndex];
        while (left <= right) {
            //交换元素
            if (array[left] >= pivot && array[right] <= pivot && array[left] > array[right]) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;
            }
            if (array[left] < pivot) {
                left++;
            }
            if (array[right] >= pivot) {
                right--;
            }
        }
        //置换pivot到中部
        array[pivotIndex] = array[left-1];
        array[left-1] = pivot;
        //递归排序
        quickSort(array, pivotIndex, pivotIndex + 1, left - 1);
        quickSort(array, left, left + 1, array.length - 1);
    }
}

堆排序(TODO)

计数排序

时间复杂度：O(m+n)，n: 数据个数，m: 数据范围
实现

public class CountingSort {
    public static void main(String[] args) {
        int[] array = new int[]{3, 8, 11, 13, 9, 2, 2, 4, 16, 3};
        countingSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    static void countingSort(int[] array) {
        //1.计算计数数组长度和偏移量
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length - 1; i++) {
            if (min > array[i]) {
                min = array[i];
            }
            if (max < array[i]) {
                max = array[i];
            }
        }
        int[] countingArray = new int[max - min + 1];
        //2.计数
        for (int i = 0; i < array.length; i++) {
            countingArray[array[i] - min]++;
        }
        //3.原数组排序
        int index = 0;
        for (int i = 0; i < countingArray.length; i++) {
            if (countingArray[i] == 0) {
                continue;
            } else {
                for (int j = 0; j < countingArray[i]; j++) {
                    array[index++] = i + min;
                }
            }
        }
    }

}

桶排序(TODO)

字符串匹配

单模式匹配

BF 算法（TODO）

RK 算法（TODO）

BM 算法（TODO）

KMP 算法

public class KMP {
    public static void main(String[] args) {
        String str = "BBC ABCDAB ABCDABCDABDE";
        String target = "ABCDABD";

//        String str = "BCBCC";
//        String target = "BCC";
        System.out.println(kmp(str, target));
    }

    /**
     * 寻找字符串内是否含有目标字符串
     *
     * @param str    字符串
     * @param target 目标字符串
     * @return 返回目标字符串在字符串中的下标值，不含则返回-1
     */
    private static int kmp(String str, String target) {
        if (str.length() <= target.length()) {
            if (str.equals(target)) {
                return 0;
            }
            return -1;
        }

        char[] strC = str.toCharArray();
        char[] targetC = target.toCharArray();
        int i = 0;
        int j = 0;
        while (i <= strC.length - targetC.length && j < targetC.length) {
            if (strC[i + j] == targetC[j]) {
                j++;
            } else {
                if (j > 1) {
                    i = i + j - getPartialNumber(target.substring(0, j));
                } else {
                    i++;
                }
                j = 0;
            }
        }
        if (j != 0) {
            return i;
        } else {
            return -1;
        }
    }

    private static int getPartialNumber(String string) {
        if (string.length() < 2) {
            return 1;
        }
        for (int i = string.length() - 1; i > 0; i--) {
            if (string.substring(0, i).equals(string.substring(string.length() - i, string.length()))) {
                return i;
            }
        }
        return 0;

    }
}

多模式匹配

Trie 树（TODO）

算法思维（TODO）

贪心算法
分治算法
回溯算法
动态规划