手写一些常见算法

- 快速排序
- 归并排序
- Dijkstra
- 自定义排序
- 交替打印0和1
- 冒泡排序
- 插入排序
- 堆排序

快速排序

java">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;}
}

归并排序

java">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

java">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;}
}

自定义排序

java">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

java">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();}}}}}
}

冒泡排序

java">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;}
}

插入排序

java">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;}}
}

堆排序

java">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);}}
}