1.二分查找

 public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {//  List<比较器> list ， 元素if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list, key);elsereturn Collections.iteratorBinarySearch(list, key);}

// 下标比较法 直接将下标带入

 private static <T>int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {int low = 0;int high = list.size()-1;while (low <= high) {int mid = (low + high) >>> 1;Comparable<? super T> midVal = list.get(mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found}

迭代器比较法 每次都得去迭代器中找到元素

int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{int low = 0;int high = list.size()-1;ListIterator<? extends Comparable<? super T>> i = list.listIterator();while (low <= high) {int mid = (low + high) >>> 1;Comparable<? super T> midVal = get(i, mid);int cmp = midVal.compareTo(key);if (cmp < 0)low = mid + 1;else if (cmp > 0)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found
}

区别，一个通过下标找，一个通过迭代器遍历找

2.反转
这个直接就是互相交换，没什么说的

  public static void reverse(List<?> list) {int size = list.size();if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)swap(list, i, j);} else {// instead of using a raw type here, it's possible to capture// the wildcard but it will require a call to a supplementary// private methodListIterator fwd = list.listIterator();ListIterator rev = list.listIterator(size);for (int i=0, mid=list.size()>>1; i<mid; i++) {Object tmp = fwd.next();fwd.set(rev.previous());rev.set(tmp);}}}

3.顺序随机分配（洗牌）

public static void shuffle(List<?> list) {Random rnd = r;if (rnd == null)r = rnd = new Random(); // harmless race.shuffle(list, rnd);
}public static void shuffle(List<?> list, Random rnd) {int size = list.size();if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {for (int i=size; i>1; i--)//每个数都得尝试动一次swap(list, i-1, rnd.nextInt(i));} else {Object[] arr = list.toArray();// Shuffle arrayfor (int i=size; i>1; i--)swap(arr, i-1, rnd.nextInt(i));// Dump array back into list// instead of using a raw type here, it's possible to capture// the wildcard but it will require a call to a supplementary// private methodListIterator it = list.listIterator();for (Object e : arr) {it.next();it.set(e);}}}

4.数据交换

public static void swap(List<?> list, int i, int j) {// instead of using a raw type here, it's possible to capture// the wildcard but it will require a call to a supplementary// private methodfinal List l = list;l.set(i, l.set(j, l.get(i)));//这里  因为set返回的是之前的值，l.set(j, l.get(i)) 这个返回的，就是之前放在index = j的值//很妙，用返回值作为参数嵌套
}E set(int index, E element);//
Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
在此列表中的指定位置插入指定的元素（可选操作）。将当前位于该位置的元素（如果有）和任何后续元素向右移动（在其索引中添加一个）Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).