14. 排序算法总结

  冒泡排序：依次比较相邻元素的排序码，若发现逆序则交换。 可以设置一个变量记录，每轮比较的时候是否有元素交换，若没有则已经有序，没有必要再继续了。（对于原本有序的数组比较好，可由平方阶时间复杂度提升至线性阶）。如果两个元素相等，无需改变他们的位置，因此冒泡排序是稳定的。

  快速排序：是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部数据分别进行快速排序。在选择比较基数时一般有（开头元素、结尾元素、中间元素、随机选择）几种方式，建议随机或者选择中间元素，因为若选择两个边界的则当序列基本有序时快排退化成冒泡。快排在交换元素的时候很可能就打乱了相等元素的相对位置，所以快排是不稳定的。

  选择排序法：第一次从 R[0]-R[n-1]中选取最小值，与 R[0]交换，第二次从 R[1]-R[n-1]中选取最小值，与R[1]交换，依次类推。在一趟选择中，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。例如，序列5 8 5 2 9，我们知道第一个元素是2，那么原序列中两个5的相对顺序就破坏了，所以选择排序是不稳定的。

  插入排序：插入排序是在一个已经有序的小序列基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素。当元素基本有序时，插入排序的比较次数会大大降低，最好情况下时间复杂度降为线性。相等的元素在插入的时候可以不改变顺序，所以插入排序是稳定的。

  归并排序：是将两个有序的序列进行合并排序（递归划分，当只有1个元素时则即是有序的）。合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。（合并的时候需要一个n长度的辅助数组），在Java的集合工具类Collections.sort(list);使用的就是基于归并的排序策略。

  希尔排序：改进的插入排序，插入排序每次的增量为1，希尔排序在元素很无序时使用较大的增量，当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。 一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同元素在各自的插入排序中移动，最后其稳定性就会被打乱。所以希尔排序是不稳定的。

  堆排序：直接选择排序的改进（将序列创建成堆之后，每次选择的堆顶元素即可）。堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程从第n/2开始和其子节点共3个值选择最大或最小，这3个值的选择当然不会破坏其稳定性。但当n/2-1，n/2-2，…，1这些父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以堆排序不是稳定的排序算法。

  基数排序：是按照低位先排序，然后收集；再按照高位排序，然后再收集； 依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

时间复杂度

  (1)、平方阶(O(n^2))排序：各类简单排序，直接插入、直接选择和冒泡排序；
  (2)、线性对数阶(O(nlog2n))排序：快速排序、堆排序和归并排序；
  (3)、O(n^(1+§)))排序，§是介于 0 和 1 之间的常数：希尔排序；
  (4)、线性阶(O(n))排序：基数排序，此外还有桶、箱排序。
  说明：当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O(n)；
  而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O(n^2)；原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性

  排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。
  稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；
  稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序；
  不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
  注意：凡是对有序甚至基本有序的序列进行操作时，都可以考虑使用二分策略（二分查找，二分插入）来提升性能。

15. Java反射机制

Java.Lang.Class

  在Java中万事万物都被抽象成为类，一个具体的事物则是某个类的实例对象，那么对Java中类的抽象呢（例如，每个类都有成员变量，构造方法，成员方法等）？对类的抽象就是类类型（class type），即Class类。
  Class类的实例就是Java中的类，Class类的构造方法是私有的，只能由Java虚拟机创建，并且每个类只有一个与之对应的Class类实例（不管用何种方式获取的都一样）。
  当一个类由JVM加载到内存中时，都会生成类对应的一个Class类的对象，（更恰当地说，是被保存在一个同名的.class文件中）。为了生成这个类的对象，运行这个程序的Java虚拟机将使用被称为“类加载器”的子系统。该Class类的对象就保存了运行时Java类的类型信息。
  1、getName()：一个Class对象描述了一个特定类的属性，Class类中最常用的方法getName，以String的形式返回此Class对象所表示的实体(类、接口、数组类、基本类型或void)名称。
  2、newInstance()：Class还有一个有用的方法可以为类创建一个实例，这个方法叫做newInstance()。newInstance()方法调用默认构造器(无参数构造器)初始化新建对象。
  3、getClassLoader()：返回该类的类加载器。
  4、getComponentType()：返回表示数组组件类型的Class。
  5、getSuperclass()：返回表示此Class所表示的实体(类、接口、基本类型或void)的超类的Class。
  6、isArray()：判定此Class对象是否表示一个数组类。

java.lang.reflect.Field

  成员变量也是对象，是java.lang.reflect.Field类的对象：
  * getFields()：获取的是所有的public的属性，包括父类继承而来的；
  * getDeclaredFields()：获取的是该类自己声明的属性，不论访问权限。

java.lang.reflect.Method

  成员方法也是对象，一个成员方法就是一个Method类的对象：
  * getMethods()：获取的是所有的public的方法，包括从父类继承而来的方法；
  * getDeclaredMethods()：获取的是所有该类自己声明的方法，不论访问权限。
  Method类中的如下几种方法：
  1、getModifiers()：以整数形式返回此 Method 对象所表示方法的 Java 语言修饰符。
  2、getReturnType()：返回一个 Class 对象，该对象描述了此Method 对象所表示的方法的正式返回类型。
  3、getName()：以 String 形式返回此 Method 对象表示的方法名称。
  4、getParameterTypes()：按照声明顺序返回 Class 对象的数组，这些对象描述了此Method 对象所表示的方法的形参类型。
  5、getExceptionTypes()：返回 Class 对象的数组，这些对象描述了声明将此Method 对象表示的底层方法抛出的异常类型。
  在这需要注意的是，利用getModifiers()获取修饰符并不是简单的输出public、static等，而是以整数形式返回所表示的方法的Java语言修饰符。可借助Modifier类的toString()方法来完成。

java.lang.reflect.Constructor

  构造函数也是对象，是java.lang.reflect.Constructor类的对象：
  getConstructors()：获取所有的public的构造函数（实际上构造函数也不能被继承，因此所有的也都是自己定义的）。
  getDeclaredConstructors()：获取自己定义的所有的构造函数。
  在Construction，Method，Field三个类中有一个共同的父类AccessibleObject，定义了取消封装的操作：setAccessible(Boolean flag)，
  public void setAccessible(boolean flag) throws SecurityException
  该方法默认的参数是false，表示反射的对象应该实施 Java 语言访问检查。值为 true 则指示反射的对象在使用时应该取消 Java 语言访问检查。所谓语言访问检查即不能通过反射来访问类的私有属性与方法，因为这样做会破坏类的封装性。实在要这样做就可以：
  setAccessible(true);

16. Java异常处理

  当出现程序无法控制的外部环境问题（如：用户提供的文件不存在，文件内容损坏，网络不可用......）时，JAVA就会用异常对象来描述。
  JAVA中用2种方法处理异常：
  1、在发生异常的地方直接处理。
  2、将异常抛给调用者，让调用者处理。

Java异常的分类

  1、检查性异常：java.lang.Exception（程序正确）
  因为外在的环境条件不满足引发。JAVA编译器强制要求处理这类异常，如果不捕获这类异常，程序将不能被编译。
  2、运行期异常：java.lang.RuntimeException
  意味着程序存在bug，如数字越界，0被除。这类异常需要更改程序来避免，JAVA编译器强制要求处理这类异常。
  3、错误：java.lang.Error
  一般很少见，也很难通过程序解决。它可能源于程序的bug，但一般更可能源于环境问题，如内存耗尽。错误在程序中无需处理，而由运行环境处理。
  java.lang.Exception和java.lang.Error继承自java.lang.Throwable，而java.lang.RuntimeException继承自java.lang.Exception。

异常处理

  1、Try....catch：程序运行产生异常时，将从异常发生点中断程序并向外抛出异常信息。
  2、Finally：如果把finally块置try...catch...语句后，finally块一般都会得到执行，它相当于一个万能的保险，即使前面的try块发生异常，而又没有对应的catch块，finally块将会马上执行。 若try语句快中存在return语句，则会在finally语句执行完再返回。（若try语句和finally中都有return，则返回的是finally语句块中的）。
  以下情形，finally块将不会被执行；
  1、finally块中发生了异常。
  2、程序所在线程死亡。
  3、前面代码使用了System.exit()；
  4、关闭CPU。
  注意：return要返回的值会存储到一个临时栈，若finally块中只是改变要返回变量的值，而不返回，则临时栈中的值不会改变。

public static int returnTry() {
    int a = 0;
    try {
        a = 1;
        return 1;

    } finally {
        // 只是改变了a的值，但是返回的还是1
        System.out.println("改变a的值！！");
        a = 2;
    }
}

public static int returnFinally() {
    int a = 0;
    try {
        a = 1;
        return 1;

    } finally {
        a = 2;
        // 返回2
        return a;
    }
}