如果有两个数组已经有序，那么可以把这两个数组归并为更大的一个有序数组。归并排序便是建立在这一基础上。要将一个数组排序，可以将它划分为两个子数组分别排序，然后将结果归并，使得整体有序。子数组的排序同样采用这样的方法排序，这个过程是递归的。

快速排序是比较经典、常用的算法，下面简要介绍其思路。对于一个数组，选取某个元素作为切分元素（比如第一个元素），然后把比这个元素小的都放到它前面，比这个元素大的都放到它后面，这样切分元素的最终位置就确定了，并且数组被划分为两个子数组。然后再用同样的方法分别对子数组进行排序，最终整个数组将变成有序的...

对冒泡排序的优化主要是减少交换次数。如果一次扫描中元素没有发生交换，那么排序就可以结束了。为此可设置一标志量flag，默认为false，如果扫描中发生交换了则把flag置为true，下轮扫描前先检查这个变量，如果flag=false则排序结束。更进一步，可以记录每次扫描中最后一次交换的位置，下次扫描的时候只要扫描到上次的最...

可以看到ArrayList继承了AbstractList抽象类，它实现了List接口的大多数方法。如果要实现一个不可变的List，只要继承这个类并且实现get(int)和size方法。如果要实现可变的List，需要覆盖set(int, E)。另外，如果List的大小是可变的，还要覆盖add(int, E)和remove()方法。