插入排序与二分查找
package com.m.test;
import java.lang.reflect.Constructor;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.CopyOnWriteArrayList;
public class Test2 {
public static void main(String[] args) {
//二分查找,加插入排序
Random random = new Random();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(random.nextInt(10));
}
System.out.println(list);
insertSort(list);
int i = binSearch(list, 0, list.size() - 1, 5);
System.out.println(i);
System.out.println(list);
}
//插入排序
public static void insertSort(List<Integer> list) {
for (int i = 0; i < list.size() - 1; i++) {
for (int j = i + 1; j > 0 &&
list.get(j) < list.get(j - 1); j--) {
swap(list, j, j - 1);
}
}
}
//二分查找是查找下标
public static int binSearch(List<Integer> list, int left, int right, int key) {
//1、获取mid
while (left <= right) {
int mid = (right + left) >>> 1;
int midVal = list.get(mid);
if (key > midVal) {
left = mid + 1;
} else if (key < midVal) {
right = mid - 1;
} else {
return mid;
}
}
return -(left + 1);
}
public static void swap(List<Integer> list, int a, int b) {
int t = list.get(a);
list.set(a, list.get(b));
list.set(b, t);
}
}
[2, 2, 6, 9, 6, 5, 9, 4, 7, 4]
4
[2, 2, 4, 4, 5, 6, 6, 7, 9, 9]
【2】CopyOnWriteArrayList
CopyOnWrite 写时复制
读写分离思想,流行框架底层思想来源于JavaSE,JavaEE
add()方法
public boolean add(E e) {
//final 重入锁
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//写时复制
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
//同步到原来的数组中
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
get()方法
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}