常见算法

什么是算法

算法是解决某个实际问题的过程和方法。

排序算法

冒泡排序

每次都从数组中找出最大值放到数组的后面去。

伪代码（升序排序）：

输入：未排序的数组arr，数组长度length
输出：无输出，数组arr原地实现排序
1 for (i = 0; i < length - 1; i++)
2     for (j = 0; j < length - i - 1; j++)
3         if (arr[i] > arr[j])
4             swap(arr[i], arr[i + 1])
5         end if
6     end for
7 end for

选择排序

每轮选择当前位置，来找出后面的较小值与该位置交换。

伪代码（升序排序）：

输入：未排序的数组arr，数组长度length
输出：无输出，数组arr原地实现排序
1 for (i = 0; i < length - 1; i++)
2     for (j = i + 1; j < length - 1; j++)
3         if (arr[i] > arr[j])
4             swap(arr[i], arr[j])
5         end if
6     end for
7 end for

查找算法

基本查找/顺序查找

遍历数组，依次比较。

在数据量特别大时，基本查找性能很差。

二分查找/折半查找

1. 将数组排序。
2. 二分法查找。

伪代码：

输入：带查找数组arr，数组长度length，待查找值data
输出：待查找值的索引index，若数组中没有待查找值，则输出None
1  left = 0, right = length - 1
2  while (left <= right)
3      middle = floor((left + right) / 2)
4      if (data < arr[middle])
5          left = middle - 1
6      else if (data > arr[middle])
7          right = middle + 1
8      else
9          return middle
10     end if
11 end while
12 return None

正则表达式

正则表达式概述

正则表达式是什么

正则表达式是由一些特定的字符组成的，代表的是一个规则。

正则表达式的作用

• 用来校验数据格式是否合法。
• 在一段文本中查找满足要求的内容。
• 在一段文本中搜索替换、分割内容。

String提供的与正则表达式相关的方法

正则表达式的书写规则

字符类（只匹配单个字符）：

预定义字符(只匹配单个字符)：

数量词：

其他：

注意：\\.代表对.的转义

补充：(任意字符)\\1代表分组编号，应用如下：

String str = "我我我喜欢编编编编编编编编编程程程";
String s = str.replaceAll("(.)\\1+", "$1");
System.out.println(s);

输出为：

我喜欢编程

异常

认识异常

异常就是程序出现的问题。

异常的体系

• Error：代表的系统级别错误(属于严重问题)，也就是说系统一旦出现问题，sun公司会把这些问题封装成Error对象给出来。开发过程中一般不会用到。
• Exception：异常，它代表的是我们程序可能出现的问题，所以，我们通常会用Exception以及它的子类来封装程序出现的问题。
  • 运行时异常：RuntimeException及其子类，编译阶段不会出现错误提醒，但运行时出现的异常（如：数组索引越界异常）。
  • 编译时异常(即其他异常)：编译阶段就会出现错误提醒的异常（如：日期解析异常）。

异常有什么用

• 异常是用来查寻系统Bug的关键参考信息。
• 异常可以作为方法内部的一种特殊返回值，以便通知上层调用者底层的执行情况。

自定义异常

Java无法为这个世界上全部的问题都提供异常类来代表， 如果开发者自己遇到了某种问题，想通过异常来表示，以便用异常来管理该问题，那就需要自己来定义异常类了。

自定义运行时异常

1. 定义一个异常类继承RuntimeException。
2. 重写构造器。
3. 通过throw new 异常类(xxx)来创建异常对象并抛出。

特点：编译阶段不报错，提醒不强烈，运行时才可能出现。

自定义编译时异常

1. 定义一个异常类继承Exception。
2. 重写构造器。
3. 通过throw new 异常类(xxx)来创建异常对象并抛出。

特点：编译阶段就报错，提醒更加强烈。

throw和throws

• throw用在方法内，抛出去这个异常对象。
• throws用在方法上，抛出方法内部的异常。

异常的处理

代码层面的处理

抛出异常（throws）

在方法上使用throws关键字，可以将方法内部出现的异常抛出去给调用者处理。

方法 throws 异常1, 异常2, 异常3... {
	...
}

// 推荐方式
方法 throws Exception {
    ...
}
// Exception代表可以捕获一切异常

捕获异常(try…catch)

直接捕获程序出现的异常。

try{
    // 监视可能出现异常的代码
} catch (异常类型1 变量) {
    // 处理异常
} catch (异常类型2 变量) {
    // 处理异常
}...

// 推荐方式
try{
    // 可能出现异常的代码
} catch (Exception e) {
    // 处理异常
}
// Exception代表可以捕获一切异常

补充：try…catch…finally

• try…catch语句后可以增加finally语句，此时无论是否捕获到了异常，都会在最后执行finally中的语句。

try{
    // 监视可能出现异常的代码
} catch (异常类型1 变量) {
    // 处理异常
} catch (异常类型2 变量) {
    // 处理异常
}...
  finally {
    //无论是否捕获到异常，最后都要执行的语句
}

• try语句后必须有至少一个catch语句或有一个finally语句或二者皆有。

开发中对于异常的常见处理方法

下层方法将异常抛出给调用者，逐层抛出直到最外层方法，最外层方法有两种处理方式：

1. 捕获异常，记录异常并响应合适的信息给用户。
2. 捕获异常，尝试重新修复。

• 抛出异常时，都只抛出Exception即可。