BV15b4y117RJ

• 二分查找

二分查找

目标：手写代码、掌握细节
细节：
1. 避免整数溢出：L+R可能超出Integer.MAX_VALUE。
方法一：改成 L/2+R/2 → L + (R-L)/2
方法二：改成位计算（无符号右移） (L+R) >>> 1
2. 变体 （详见leetcode）

排序

目标：掌握思路，手写代码，了解特性（时间复杂度、是否稳定）

冒泡排序

（升序）每轮 依次比较相邻两个元素的大小，若a[j]>a[j+1]则交换位置，使得最大的元素排到最后
优化：
1. 减少比较次数（每轮冒泡的比较次数递减）
2. 减少冒泡次数（发现本轮没有进行交换，说明数组整个都有序了不用再排序了），
3. 进一步优化：记录每轮的最后一次进行交换的索引，来得到下轮的比较次数。若为0这说明全排完了（相当于优化2）

选择排序

（升序）每轮选择出数组后部分中最小的元素，移到数组前部分
i代表每轮选择最小元素要交换到的目标索引

选择排序vs冒泡排序

稳定：相同元素不会打乱位置

插入排序

数组开头保持为有序的。把后面的元素一个一个插入到开头的有序组中。
性质：稳定的

缺点：很大的元素位于前面的话，要移动很多次位置才能到达目标位置希尔排序
改进了插入排序。把整个数组按一定间隔分组，分别进行插入排序插入和选择—推导第n轮后的结果

快速排序

1.每一轮排序选择一个基准点(pivot)进行分区
1.让小于基准点的元素的进入一个分区,大于基准点的元素的进入另一个分区2.当分区完成时,基准点元素的位置就是其最终位置
2.在子分区内重复以上过程,直至子分区元素个数少于等于1,这体现的是分而治之的思想(divide-and-conquer)

快排的实现

• 单边循环快排（Lomuto）：

  • pivot：最右元素
  • j指针负责找到比pivot小的元素，一旦找到则与i进行交换；i指针维护小于pivot的边界，即每次交换的目标索引
  • 最后pivot和i交换，i即为分区位置
    

• 双边循环快排：

  • pivot：最左元素
  • j指针负责从右向左找比pivot小的元素，i指针负责从左向右找比基准点大的元素，一旦找到则两者交换，直到i、j相交
  • 最后pivot和i交换，i即为分区位置
  • 霍尔

快排的特点数据量特别大的时候用快排，其中分区长度比较小的时候用插排

集合—ArrayList

扩容机制

初始化：

• ArrayList() 长度为0
• ArrayList(int initialCapacity) 使用指定容量的数组
• public ArrayList(Collection<? extends E> c)使用c的大小作为容量

添加元素超出容量时会扩容。

• 添加一个元素 L.add 每次扩容成1.5倍
• 添加一个集合的全部元素 L1.addAll(L2) ① L1是空list 扩容成max(10,实际元素个数) ② L1非空 扩容成max(L1的1.5倍，实际元素个数)Iterator

遍历

• fail-fast
  一旦发现遍历时其他人来修改，则抛异常
  ArrayList用modCount记录修改次数，遍历中检查发现modCount与预期不符则说明被修改过了，终止遍历

• fail-safe（CopyOnWriteArrayList）
  允许修改，牺牲一致性（以老数据为准）让遍历完成

------------恢复内容结束------------