快速排序

public class Main {public static void main(String[] args) {int nums[] = {1,3,2,5,4,6,8,7,9};quickSort(nums,0,nums.length - 1);}private static void quickSort(int[] nums, int left, int right) {if(left >= right)return;// 劃分數組 得到以privot為中心的數組 左小于privot 右大于privotint privot = partition(nums, left, right);// 遞歸左邊和右邊quickSort(nums, left, privot - 1);quickSort(nums,privot + 1, right);}private static int partition(int[] nums, int left, int right) {// 選基準int p = nums[right];// 指向大于等于基準元素的前一個位置int l = left - 1;for(int r = 0; r < right; r++){if(nums[r] < p){l++;int tmp = nums[r];nums[r] = nums[l];nums[l] = tmp;}}// 再對基準元素放置l+1處，因為l是指向前一個大于等于基準的位置nums[right] = nums[l + 1];nums[l + 1] = p;return l + 1;}
}

歸并排序

public class QuickAndMerge {static int res = 0;public static void main(String[] args) {int nums[] = {1,3,2,5,4,6,8,7,9};int res[] = mergeSort(nums, 0, nums.length - 1);quickSort(nums,0,nums.length - 1);}private static int[] mergeSort(int nums[], int left, int right){// 當排序長度為1，直接返回對應元素if(left == right)return new int[]{nums[left]};// 劃分int mid = (right - left)/2 + left;int l[] = mergeSort(nums, left, mid);int r[] = mergeSort(nums, mid + 1, right);return mergeTwoArray(l,r);}private static int[] mergeTwoArray(int l[], int r[]){int res[] = new int[l.length + r.length];int num = 0;int l_num = 0;int r_num = 0;// 依次選取兩數組中較小的元素while(l_num < l.length && r_num < r.length){res[num++] = l[l_num] < r[r_num] ? l[l_num++]:r[r_num++];}// 處理剩余元素while(l_num < l.length){res[num++] = l[l_num++];}while(r_num < r.length){res[num++] = r[r_num++];}return res;}

Dijkstra

public class Main{public static void main(String[] args) {int n = Integer.MAX_VALUE/2;int node[] = {1,2,3,4,5};int matrix[][] = new int[node.length + 1][node.length + 1];matrix[1] = new int[]{n, 0, 1, n, 3, n};matrix[2] = new int[]{n, n, 0, 3, 1, n};matrix[3] = new int[]{n, n, n, 0, n, 1};matrix[4] = new int[]{n, n, n, 1, 0, n};matrix[5] = new int[]{n, n, n, n, n, 0};// 求1到其它點的最短距離int distance[] = {n, 0, n, n, n, n};// 每次從一點開始搜索boolean accessed[] = new boolean[node.length + 1];// 共node.length個點for(int i = 0; i < node.length; i++){int curIndex = findMin(distance, accessed);accessed[curIndex] = true;// 如果有更短路徑則更新for(int j = 1; j < distance.length; j++){if(curIndex != j && distance[j] > matrix[curIndex][j] + distance[curIndex]){distance[j] = matrix[curIndex][j] + distance[curIndex];}}}System.out.println(distance[5]);}// 找最小distance的一個，易得起始節點到此點的距離已最小，可以開始對其鄰居進行訪問private static int findMin(int[] distance, boolean[] accessed) {int index = 1;int min = Integer.MAX_VALUE;for(int i = 1; i < distance.length; i++){if(!accessed[i] && min > distance[i]){min = distance[i];index = i;}}return index;}
}

自定義排序

import java.util.Arrays;
import java.util.Comparator;
public class Student{int score;int age;Student(int score, int age){this.score = score;this.age = age;}public int getScore() {return score;}public void setNum(int score) {this.score = score;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public static void main(String[] args) {Student stu[] = new Student[3];stu[0] = new Student(1,2);stu[1] = new Student(1,0);stu[2] = new Student(2,0);// 寫法1 匿名內部類Arrays.sort(stu, new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {if(o1.getScore() != o2.getScore())return o2.getScore() - o1.getScore();return o1.getAge() - o2.getAge();}});// 寫法2 lambdaArrays.sort(stu, ((o1, o2) -> {if(o1.getScore() != o2.getScore())return o2.getScore() - o1.getScore();return o1.getAge() - o2.getAge();}));// 寫法3Arrays.sort(stu, Comparator.comparing(Student::getScore).reversed().thenComparing(Student::getAge));}
}

交替打印0和1

public class Main{private static final Object lock = new Object();private static int count = 0;private static final int MAX = 200;public static void main(String[] args) {// 創建線程 將實現了Runnable接口的printer放入，start啟動Thread thread1 = new Thread(new Printer(), "線程1");Thread thread2 = new Thread(new Printer(), "線程2");thread1.start();thread2.start();}static class Printer implements Runnable {// 重寫Run方法@Overridepublic void run() {while (true) {// synchronizedsynchronized (lock) {// 打印完成if (count > MAX) {break;}System.out.println(Thread.currentThread().getName() + "打印數字: " + count++);// 喚醒等待鎖的線程lock.notify();try {if (count <= MAX) {lock.wait();}} catch (InterruptedException e) {Thread.currentThread().interrupt();}}}}}
}

冒泡排序

public class BubbleSort {public static void main(String[] args) {int bubble[] = {8,7,6,5,4,3,2,1};//bubbleSort(bubble);bubbleSortDesc(bubble);}private static void bubbleSort(int[] bubble) {for(int i = 0; i < bubble.length; i++){int flag = 0;for(int j = 0; j < bubble.length - i - 1; j++){if(bubble[j] < bubble[j + 1]){swap(bubble, j, j + 1);flag = 1;}}if(flag == 0)break;}}private static void bubbleSortDesc(int[] bubble) {for(int i = 0; i < bubble.length; i++){int flag = 0;for(int j = 0; j < bubble.length - i - 1; j++){if(bubble[j] > bubble[j + 1]){swap(bubble, j, j + 1);flag = 1;}}if(flag == 0)break;}}private static void swap(int bubble[], int i, int j){int temp = bubble[i];bubble[i] = bubble[j];bubble[j] = temp;}
}

插入排序

public class InsertSort {public static void main(String[] args) {int insert[] = {1,4,2,6,3,5,8,7};insertSort(insert);}private static void insertSort(int[] insert) {for(int i = 1; i < insert.length; i++){int i2 = i;int temp = insert[i2];while (i2 > 0 && temp < insert[i2 - 1]){insert[i2] = insert[i2 - 1];i2--;}insert[i2] = temp;}}
}

堆排序

public class HeapSort {public static void main(String[] args) {int nums[] = {1,3,4,2,6,5};heapSort(nums);}public static void heapSort(int[] nums) {int n = nums.length;// 挑整數組位置，使得父節點大于子節點，從最后一個非葉子節點開始for (int i = n / 2 - 1; i >= 0; i--) {adjust(nums, n, i);}// 依次從堆中提取元素，for (int i = n - 1; i > 0; i--) {// 將當前父節點移動到末尾int tmp = nums[0];nums[0] = nums[i];nums[i] = tmp;// 移動到末尾后繼續調整堆adjust(nums, i, 0);}}private static void adjust(int[] nums, int n, int i) {// i表示父節點int largest = i;int left = 2 * i + 1; // 左子節點int right = 2 * i + 2; // 右子節點// 如果左子節點大于根節點if (left < n && nums[left] > nums[largest]) {largest = left;}// 如果右子節點大于當前最大值if (right < n && nums[right] > nums[largest]) {largest = right;}// 如果最大值不是根節點 交換節點位置，使得較大一方到父節點位置if (largest != i) {int tmp = nums[i];nums[i] = nums[largest];nums[largest] = tmp;// 調整交換后子節點所在的子樹adjust(nums, n, largest);}}
}