▐ 手写归并
public static void merge(int[] arr, int L, int M, int R) { int[] help = new int[R - L + 1]; int i = 0; int p1 = L; int p2 = M + 1; while (p1 <= M && p2 <= R) help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; while (p1 <= M) help[i++] = arr[p1++]; while (p2 <= R) help[i++] = arr[p2++]; for (i = 0; i < help.length; i++) arr[L + i] = help[i]; } public static void mergeSort(int[] arr, int L, int R) { if (L == R) return; int mid = L + ((R - L) >> 1); process(arr, L, mid); process(arr, mid + 1, R); merge(arr, L, mid, R); } public static void main(String[] args) { int[] arr1 = {9,8,7,6,5,4,3,2,1}; mergeSort(arr, 0, arr.length - 1); printArray(arr); }
▐ 手写堆排
// 堆排序额外空间复杂度O(1) public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) return; for (int i = arr.length - 1; i >= 0; i--) heapify(arr, i, arr.length); int heapSize = arr.length; swap(arr, 0, --heapSize); // O(N*logN) while (heapSize > 0) { // O(N) heapify(arr, 0, heapSize); // O(logN) swap(arr, 0, --heapSize); // O(1) } } // arr[index]刚来的数，往上 public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } // arr[index]位置的数，能否往下移动 public static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; // 左孩子的下标 while (left < heapSize) { // 下方还有孩子的时候 // 两个孩子中，谁的值大，把下标给largest // 1）只有左孩子，left -> largest // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest int largest = left+1 < heapSize && arr[left+1]> arr[left] ? left+1 : left; // 父和较大的孩子之间，谁的值大，把下标给largest largest = arr[largest] > arr[index] ? largest : index; if (largest == index) break; swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr1 = {9,8,7,6,5,4,3,2,1}; heapSort(arr1); printArray(arr1); }
▐ 手写LRUcache
// 基于linkedHashMap public class LRUCache { private LinkedHashMap<Integer,Integer> cache; private int capacity; //容量大小 public LRUCache(int capacity) { cache = new LinkedHashMap<>(capacity); this.capacity = capacity; } public int get(int key) { //缓存中不存在此key，直接返回 if(!cache.containsKey(key)) { return -1; } int res = cache.get(key); cache.remove(key); //先从链表中删除 cache.put(key,res); //再把该节点放到链表末尾处 return res; } public void put(int key,int value) { if(cache.containsKey(key)) { cache.remove(key); //已经存在，在当前链表移除 } if(capacity == cache.size()) { //cache已满，删除链表头位置 Set<Integer> keySet = cache.keySet(); Iterator<Integer> iterator = keySet.iterator(); cache.remove(iterator.next()); } cache.put(key,value); //插入到链表末尾 } } //手写双向链表 class LRUCache { class DNode { DNode prev; DNode next; int val; int key; } Map<Integer, DNode> map = new HashMap<>(); DNode head, tail; int cap; public LRUCache(int capacity) { head = new DNode(); tail = new DNode(); head.next = tail; tail.prev = head; cap = capacity; } public int get(int key) { if (map.containsKey(key)) { DNode node = map.get(key); removeNode(node); addToHead(node); return node.val; } else { return -1; } } public void put(int key, int value) { if (map.containsKey(key)) { DNode node = map.get(key); node.val = value; removeNode(node); addToHead(node); } else { DNode newNode = new DNode(); newNode.val = value; newNode.key = key; addToHead(newNode); map.put(key, newNode); if (map.size() > cap) { map.remove(tail.prev.key); removeNode(tail.prev); } } } public void removeNode(DNode node) { DNode prevNode = node.prev; DNode nextNode = node.next; prevNode.next = nextNode; nextNode.prev = prevNode; } public void addToHead(DNode node) { DNode firstNode = head.next; head.next = node; node.prev = head; node.next = firstNode; firstNode.prev = node; } }
▐ 手写线程池
package com.concurrent.pool; import java.util.HashSet; import java.util.Set; import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; public class MySelfThreadPool { //默认线程池中的线程的数量 private static final int WORK_NUM = 5; //默认处理任务的数量 private static final int TASK_NUM = 100; private int workNum;//线程数量 private int taskNum;//任务数量 private final Set<WorkThread> workThreads;//保存线程的集合 private final BlockingQueue<Runnable> taskQueue;//阻塞有序队列存放任务 public MySelfThreadPool() { this(WORK_NUM, TASK_NUM); } public MySelfThreadPool(int workNum, int taskNum) { if (workNum <= 0) workNum = WORK_NUM; if (taskNum <= 0) taskNum = TASK_NUM; taskQueue = new ArrayBlockingQueue<>(taskNum); this.workNum = workNum; this.taskNum = taskNum; workThreads = new HashSet<>(); //启动一定数量的线程数，从队列中获取任务处理 for (int i=0;i<workNum;i++) { WorkThread workThread = new WorkThread("thead_"+i); workThread.start(); workThreads.add(workThread); } } public void execute(Runnable task) { try { taskQueue.put(task); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } } public void destroy() { System.out.println("ready close thread pool..."); if (workThreads == null || workThreads.isEmpty()) return ; for (WorkThread workThread : workThreads) { workThread.stopWork(); workThread = null;//help gc } workThreads.clear(); } private class WorkThread extends Thread{ public WorkThread(String name) { super(); setName(name); } @Override public void run() { while (!interrupted()) { try { Runnable runnable = taskQueue.take();//获取任务 if (runnable !=null) { System.out.println(getName()+" readyexecute:"+runnable.toString()); runnable.run();//执行任务 } runnable = null;//help gc } catch (Exception e) { interrupt(); e.printStackTrace(); } } } public void stopWork() { interrupt(); } } } package com.concurrent.pool; public class TestMySelfThreadPool { private static final int TASK_NUM = 50;//任务的个数 public static void main(String[] args) { MySelfThreadPool myPool = new MySelfThreadPool(3,50); for (int i=0;i<TASK_NUM;i++) { myPool.execute(new MyTask("task_"+i)); } } static class MyTask implements Runnable{ private String name; public MyTask(String name) { this.name = name; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public void run() { try { Thread.sleep(1000); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } System.out.println("task :"+name+" end..."); } @Override public String toString() { // TODO Auto-generated method stub return "name = "+name; } } }
