系列文章目录

本系列文章主要面向马上要进行算法实习，就业，跳槽的友友们。

本系列文章暂时不会进行实例解析，只提供模板，目的是以最快的速度给这些友友们提供尽可能的帮助！

1、堆排序

// 堆排序额外空间复杂度O(1)public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// O(N*logN)//for (int i = 0; i < arr.length; i++) { // O(N)//heapInsert(arr, i); // O(logN)//}// O(N)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 -> largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// 父和较大的孩子之间，谁的值大，把下标给largestlargest = 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;}

2、归并排序

// 递归方法实现public static void mergeSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}// 请把arr[L..R]排有序// l...r N// T(N) = 2 * T(N / 2) + O(N)// O(N * logN)public static void process(int[] arr, int L, int R) {if (L == R) {// base casereturn;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}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++];}// 要么p1越界了，要么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 mergeSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;// 步长int mergeSize = 1;while (mergeSize < N) {// log N// 当前左组的，第一个位置int L = 0;while (L < N) {if (mergeSize >= N - L) {break;}int M = L + mergeSize - 1;int R = M + Math.min(mergeSize, N - M - 1);merge(arr, L, M, R);L = R + 1;}// 防止溢出if (mergeSize > N / 2) {break;}mergeSize <<= 1;}}

3、由归并排序衍生出来的小和问题

public static int smallSum(int[] arr) {if (arr == null || arr.length < 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序，也要求小和返回// 所有merge时，产生的小和，累加// 左 排序 merge// 右 排序 merge// mergepublic static int process(int[] arr, int l, int r) {if (l == r) {return 0;}// l < rint mid = l + ((r - l) >> 1);returnprocess(arr, l, mid)+process(arr, mid + 1, r)+merge(arr, l, mid, r);}public static int 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;int res = 0;while (p1 <= m && p2 <= r) {res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;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];}return res;}

4、由归并排序衍生出来的逆序对问题

public static int reverPairNumber(int[] arr) {if (arr == null || arr.length < 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序，也要求逆序对数量返回// 所有merge时，产生的逆序对数量，累加，返回// 左 排序 merge并产生逆序对数量// 右 排序 merge并产生逆序对数量public static int process(int[] arr, int l, int r) {if (l == r) {return 0;}// l < rint mid = l + ((r - l) >> 1);return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);}public static int merge(int[] arr, int L, int m, int r) {int[] help = new int[r - L + 1];int i = help.length - 1;int p1 = m;int p2 = r;int res = 0;while (p1 >= L && p2 > m) {res += arr[p1] > arr[p2] ? (p2 - m) : 0;help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];}while (p1 >= L) {help[i--] = arr[p1--];}while (p2 > m) {help[i--] = arr[p2--];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}return res;}

5、两个队列实现栈

public static class TwoQueueStack<T> {public Queue<T> queue;public Queue<T> help;public TwoQueueStack() {queue = new LinkedList<>();help = new LinkedList<>();}public void push(T value) {queue.offer(value);}public T poll() {while (queue.size() > 1) {help.offer(queue.poll());}T ans = queue.poll();Queue<T> tmp = queue;queue = help;help = tmp;return ans;}public T peek() {while (queue.size() > 1) {help.offer(queue.poll());}T ans = queue.poll();help.offer(ans);Queue<T> tmp = queue;queue = help;help = tmp;return ans;}public boolean isEmpty() {return queue.isEmpty();}}

6、两个栈实现队列

public static class TwoStacksQueue {public Stack<Integer> stackPush;public Stack<Integer> stackPop;public TwoStacksQueue() {stackPush = new Stack<Integer>();stackPop = new Stack<Integer>();}// push栈向pop栈倒入数据private void pushToPop() {if (stackPop.empty()) {while (!stackPush.empty()) {stackPop.push(stackPush.pop());}}}public void add(int pushInt) {stackPush.push(pushInt);pushToPop();}public int poll() {if (stackPop.empty() && stackPush.empty()) {throw new RuntimeException("Queue is empty!");}pushToPop();return stackPop.pop();}public int peek() {if (stackPop.empty() && stackPush.empty()) {throw new RuntimeException("Queue is empty!");}pushToPop();return stackPop.peek();}}