插入排序与二分查找与CopyOnWrite 写时复制思想

插入排序与二分查找

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];
}