參考文章

快速排序

public class Solution {private static int partition(int[] arr, int left, int right) {int temp = arr[left];	// 1while(left < right) {while(left < right && temp <= arr[right]) right--;arr[left] = arr[right];	// 2while(left < right && temp >= arr[left]) left++;arr[right] = arr[left];	// 3}arr[left] = temp;	// 4return left;}private static void quicSort(int[] arr, int left, int right) {if(left<right) {int mid = partition(arr, left, right);quicSort(arr,left, mid-1);quicSort(arr,mid+1, right);}}public static void main(String[] args) {int[] arr = {3,5,1,32,8,5,3,0};quicSort(arr, 0, arr.length-1);Arrays.stream(arr).forEach((n)->{System.out.print(n + " ");});}
}

• 時間復雜度O($nlogn$)：快排使用的是遞歸，需要做logn次分割，而每次劃分需要找對應的基準元素，需要O(n)時間。
• 空間復雜度O($logn$)：平均情況下，遞歸樹的高度為logn。

歸并排序

public class Solution {// 主要是這里，對于兩個有序數組合并，是挺簡單的。// 如何把它拆分出來是一個問題。private static int[] mergeSort(int[] arr, int left, int right) {if(left == right) { //長度為1，直接放回return new int[]{arr[left]};}int mid = ((right - left) >> 1 ) + left;int[] l = mergeSort(arr, left, mid);int[] r = mergeSort(arr, mid+1, right);return mergeTwoArray(l,r);}// 歸并思想挺簡單的，如下private static int[] mergeTwoArray(int[] l, int[] r) {int[] res = new int[l.length+r.length];int left = 0, right = 0, index = 0;while(left < l.length && right < r.length) {if(l[left] < r[right]) {res[index++] = l[left++];}else {res[index++] = r[right++];}}while(left < l.length) {res[index++] = l[left++];}while(right < r.length) {res[index++] = r[right++];}return res;}public static void main(String[] args) {int[] arr = {3,5,1,32,8,5,3,0};int[] res = mergeSort(arr, 0, arr.length-1);    // 注意這里不是原地排序的，是新開辟一個空間Arrays.stream(res).forEach((n)->{System.out.print(n + " ");});}
}

• 時間復雜度O($nlogn$)：無論原始數組的順序如何，歸并排序都需要將數組不斷地分成兩半，然后再合并，總共需要進行logn
  層的劃分和合并操作，每層操作都需要遍歷 O(n)個元素。

• 空間復雜度O($n$)：需要額外的輔助數組。

Dijkstra

package com.zy;import java.util.Arrays;public class Solution {private static final int INF = Integer.MAX_VALUE;public static int[] dijkstra(int[][] graph, int src) {int n = graph.length;int[] dist = new int[n];boolean[] sptSet = new boolean[n];//初始化距離數組和最短路徑集合Arrays.fill(dist, INF);dist[src] = 0;// 每次循環找到距離src最近的一個節點，總共循環n-1次for (int count = 0; count < n - 1; count++) {//找到最近節點uint u = minDistance(dist, sptSet);sptSet[u] = true;// 加入u后，各個節點的變化for (int v = 0; v < n; v++) {// 要是還沒處理，且u和v是可達的，且剛剛更新的最近節點u不是不可達的，且更新后的距離更短if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}return dist;}private static int minDistance(int[] dist, boolean[] sptSet) {int min = INF, minIndex = -1;for (int v = 0; v < dist.length; v++) {if (!sptSet[v] && dist[v] <= min) {min = dist[v];minIndex = v;}}return minIndex;}public static void main(String[] args) {int[][] graph = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};int src = 0;int[] dist = dijkstra(graph, src);System.out.println("從頂點 " + src + " 到各頂點的最短距離為：");for (int i = 0; i < dist.length; i++) {System.out.println("到頂點 " + i + " 的最短距離是：" + dist[i]);}}
}

• 時間復雜度O($n^2$)：由于使用了鄰接矩陣存儲圖，每次查找距離源點最近的頂點需要遍歷所有頂點，更新距離也需要遍歷所有頂點。
• 空間復雜度O($n$)：主要使用了 dist 數組和 sptSet 數組來存儲距離和標記頂點是否已處理

自定義排序

思考Comparator和Comparable的區別

實現Comparator接口實現。

package com.zy;import java.util.Arrays;
import java.util.Comparator;class Student implements Comparable<Student>{int age;int score;public Student(int age, int score) {this.age = age;this.score = score;}@Overridepublic int compareTo(Student o) {if(this.age != o.age) {return this.age - o.age;}return o.score - this.score;}
}public class Solution {public static void main(String[] args) {Student[] stu = new Student[3];stu[0] = new Student(10,13);stu[1] = new Student(5, 4);stu[2] = new Student(5,33);// 法1Arrays.sort(stu, new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {if(o1.age != o2.age) {return o1.age - o2.age;}return o2.score - o1.score;}});// 法2Arrays.sort(stu, (o1,o2)-> {if(o1.age != o2.age) {return o1.age - o2.age;}return o2.score - o1.score;});// 法3(用Comparable實現默認排序)Arrays.sort(stu);Arrays.stream(stu).forEach(student -> {System.out.println(student.age + " " + student.score);});}
}

交替打印奇偶數

package com.zy;class AlterPrint {private static final Object lock = new Object();private static final int MAX = 200;private static int count = 0;// 打印，喚醒，看有沒有終止，有就結束，沒有就等待void printNumber() {synchronized (lock) {while(true) {System.out.println(Thread.currentThread().getName() + "打印" + count++);lock.notify();if(count>=MAX) {lock.notifyAll(); //在徹底退出之前，最好都喚醒，不然某些線程會一直等待。break;}try {lock.wait();}catch (InterruptedException e) {e.printStackTrace();}}}}}public class Solution {public static void main(String[] args) {// 實現兩個線程交替打印奇偶AlterPrint alterPrint = new AlterPrint();Thread thread0 = new Thread(alterPrint::printNumber, "線程1");Thread thread1 = new Thread(alterPrint::printNumber, "線程2");thread0.start();thread1.start();}}

冒泡排序

public class Solution {private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private static void bubbleSort(int[] arr) {for(int i=0;i<arr.length;i++) {boolean flag = true;for(int j=arr.length-1;j>i;j--) {if(arr[j-1] > arr[j]) {swap(arr, j-1, j);flag = false;}}if(flag) break;}}public static void main(String[] args) {int[] arr = {3,4,6,8,3,1,0,22,10};bubbleSort(arr);for(int i : arr) {System.out.println(i);}}}

插入排序

public class Solution {private static void InsertSort(int[] arr) {for(int i=1;i<arr.length;i++) {int key = arr[i];   // 要排序的數字int j = i-1;    // 從有序數組的尾部開始比較while(j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = {3,4,6,8,3,1,0,22,10};InsertSort(arr);for(int i : arr) {System.out.println(i);}}
}

堆排序

package com.zy;import java.util.Scanner;public class Main {// 調整有效大小為n的堆中的i節點private static void adjust(int[] nums, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// 找左右節點跟節點i中最大的節點索引 ： largestif(left < n && nums[left] > nums[largest]) {largest = left;}if(right < n && nums[right] > nums[largest]) {largest = right;}if(largest != i) {  // 如果節點i需要往下調整// 跟最大的節點替換后int tmp = nums[i];nums[i] = nums[largest];nums[largest] = tmp;// 接著繼續向下調整adjust(nums,n,largest);}}private static void heapSort(int[] arr) {int n = arr.length;// 調整數組，使得父節點>子節點，從最后一個非葉子節點開始for(int i=n/2-1;i>=0;i--) {     // 自己小推一下就知道了adjust(arr, n, i);}// i*2-1for(int i=n-1;i>0;i--) {// 當前父節點移動到末尾（這里他就是排到正確位置了）int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 剩下部分繼續調整adjust(arr, i, 0);}}public static void main(String[] args) {int[] arr = {3,1,2,5,7,4};heapSort(arr);for(int num : arr) {System.out.print(num + " ");}}
}

歐幾里得算法求最大公約數

static int gcb(int a, int b) {if(b==0) return a;return gcb(b, a%b);
}

單例模式的雙重校驗

package com.zy;public class Singleton {private volatile static Singleton singletonInstance;private Singleton(){}public static Singleton getSingleton(){if(singletonInstance == null) {synchronized (Singleton.class) {if(singletonInstance == null) {singletonInstance = new Singleton();}}}return singletonInstance;}
}

LRU