快速排序
时间复杂度：最好情况O(nlong(n)),最坏情况O(n^2)
思路：选择一个基准，将比他小的挪到他的前边，比他大的挪到他的后边
public class Main {
private static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int i = l - 1;
int j = r + 1;
int x = arr[l+r>>1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr,l,j);
quickSort(arr,j+1,r);
}
public static void main(String[] args) {
int[] arr = {3, 7, 2, 9, 1, 5, 8, 6};
quickSort(arr,0,arr.length-1);
for(int num : arr){
System.out.println(num);
}
}
}
归并排序
时间复杂度：最佳情况（O(n log n)），平均情况（O(n log n)），最差情况（O(n log n)）
采用分治的思想，先局部有序再整体有序
public class Main {
private static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int[] res = new int[arr.length];
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
int num = 0;
int i = l;
int j = mid + 1;
while (i <= mid && j <= r) {
if (arr[i] < arr[j]) res[num++] = arr[i++];
else res[num++] = arr[j++];
}
while (i <= mid) res[num++] = arr[i++];
while (j <= r) res[num++] = arr[j++];
for (i = l, j = 0; i <= r; i++, j++) {
arr[i] = res[j];
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 2, 5, 6, 0};
mergeSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.println(num);
}
}
}
单例模式
public class Main {
public static void main(String[] args) {
// 创建多个线程来获取单例实例
Runnable task = () -> {
Singleton singleton = Singleton.getInstance();
singleton.showMessage();
};
// 创建10个线程并启动它们
for (int i = 0; i < 10; i++) {
new Thread(task).start();
}
}
}
class Singleton {
// volatile 关键字确保 instance 的可见性和禁止指令重排序
private static volatile Singleton instance = null;
// 私有构造函数，防止实例化
private Singleton() {
// 可以在这里初始化一些资源
}
// 获取单例实例的方法，使用双重检查锁定
public static Singleton getInstance() {
if (instance == null) { // 第一次检查:如果实例已被创建，就直接返回实例，避免了不必要的加锁操作。
synchronized (Singleton.class) { // 加锁只有在第一次检查确定 instance 为 null 时，才进入同步块。
if (instance == null) { // 第二次检查在同步块内再次检查 instance 是否为 null，确保只有一个线程能够创建实例。
instance = new Singleton();
}
}
}
return instance;
}
// 一个简单的方法，用于测试单例类的功能
public void showMessage() {
System.out.println("Hello, I am a singleton!");
}
}
public enum Singleton {
// 定义枚举实例，这个就是单例对象
INSTANCE;
// 单例类的成员方法
public void showMessage() {
System.out.println("Hello, I am a singleton using Enum!");
}
}
public class Main {
public static void main(String[] args) {
// 获取单例实例并调用方法
Singleton singleton = Singleton.INSTANCE;
singleton.showMessage();
// 验证多个线程访问是否是同一个实例
Runnable task = () -> {
Singleton s = Singleton.INSTANCE;
System.out.println("Instance: " + s.hashCode());
};
// 启动多个线程进行验证
for (int i = 0; i < 10; i++) {
new Thread(task).start();
}
}
}
多线程交替打印奇偶数
public class Main {
private static final int max = 10;
private static final Object lock = new Object();
private static boolean isOddTurn = true; // 标识当前是否应该打印奇数
public static void main(String[] args) {
Thread thread1 = new Thread(() -> {
for (int i = 1; i <= max; i += 2) {
synchronized (lock) {
while (!isOddTurn) {
try {
lock.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("奇数:" + i);
isOddTurn = false;
lock.notify(); // 唤醒偶数线程
}
}
});
Thread thread2 = new Thread(() -> {
for (int i = 2; i <= max; i += 2) {
synchronized (lock) {
while (isOddTurn) {
try {
lock.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("偶数:" + i);
isOddTurn = true;
lock.notify(); // 唤醒偶数线程
}
}
});
thread1.start();
thread2.start();
}
}
信号量机制的实现方法
public class Main {
private static final int MAX = 10; // 打印的最大数字
private static final Object lock = new Object();
private static boolean isOddTurn = true; // 标识当前是否应该打印奇数
public static void main(String[] args) {
// 奇数线程
Thread oddThread = new Thread(() -> {
for (int i = 1; i <= MAX; i += 2) {
synchronized (lock) {
while (!isOddTurn) { // 如果不是奇数线程的执行时机，则等待
try {
lock.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("奇数: " + i);
isOddTurn = false; // 该偶数线程执行了
lock.notify(); // 唤醒偶数线程
}
}
});
// 偶数线程
Thread evenThread = new Thread(() -> {
for (int i = 2; i <= MAX; i += 2) {
synchronized (lock) {
while (isOddTurn) { // 如果不是偶数线程的执行时机，则等待
try {
lock.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("偶数: " + i);
isOddTurn = true; // 该奇数线程执行了
lock.notify(); // 唤醒奇数线程
}
}
});
// 启动两个线程
oddThread.start();
evenThread.start();
}
}
三个线程交替打印
public class ThreeThreadPrinter {
private static final int MAX = 9; // 每个线程打印的最大数字
private static final Object lock = new Object();
private static int current = 1; // 当前应该由哪个线程打印，1表示线程1，2表示线程2，3表示线程3
public static void main(String[] args) {
// 线程1，打印1, 4, 7
Thread t1 = new Thread(() -> {
for (int i = 1; i <= MAX; i += 3) {
synchronized (lock) { // 获取锁
while (current != 1) { // 如果不是线程1的执行时机，则等待
try {
lock.wait(); // 进入等待状态
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("Thread 1: " + i); // 打印数字
current = 2; // 设置为线程2的执行时机
lock.notifyAll(); // 唤醒其他线程
}
}
});
// 线程2，打印2, 5, 8
Thread t2 = new Thread(() -> {
for (int i = 2; i <= MAX; i += 3) {
synchronized (lock) { // 获取锁
while (current != 2) { // 如果不是线程2的执行时机，则等待
try {
lock.wait(); // 进入等待状态
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("Thread 2: " + i); // 打印数字
current = 3; // 设置为线程3的执行时机
lock.notifyAll(); // 唤醒其他线程
}
}
});
// 线程3，打印3, 6, 9
Thread t3 = new Thread(() -> {
for (int i = 3; i <= MAX; i += 3) {
synchronized (lock) { // 获取锁
while (current != 3) { // 如果不是线程3的执行时机，则等待
try {
lock.wait(); // 进入等待状态
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
System.out.println("Thread 3: " + i); // 打印数字
current = 1; // 设置为线程1的执行时机
lock.notifyAll(); // 唤醒其他线程
}
}
});
// 启动三个线程
t1.start();
t2.start();
t3.start();
}
}
0-1背包
public class Main {
// 0-1背包问题的解决方法
public static int bagValue(int[] weights, int[] values, int capacity) {
int n = weights.length;
// 创建一个二维数组dp，其中dp[i][j]表示前i件物品在总容量为j的条件下的最大价值
int[][] dp = new int[n + 1][capacity + 1];
// 遍历每一个物品
for (int i = 1; i <= n; i++) {
// 遍历每一个可能的容量值
for (int j = 1; j <= capacity; j++) {
// 如果当前物品的重量大于当前的背包容量，那么当前物品不能放入背包
if (weights[i - 1] > j) {
dp[i]