柚子快報(bào)激活碼778899分享：手寫(xiě)一些常見(jiàn)算法

http://yzkb.51969.com/

手寫(xiě)一些常見(jiàn)算法

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

快速排序

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;

// 劃分?jǐn)?shù)組 得到以privot為中心的數(shù)組 左小于privot 右大于privot

int 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) {

// 選基準(zhǔn)

int p = nums[right];

// 指向大于等于基準(zhǔn)元素的前一個(gè)位置

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;

}

}

// 再對(duì)基準(zhǔn)元素放置l+1處，因?yàn)閘是指向前一個(gè)大于等于基準(zhǔn)的位置

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){

// 當(dāng)排序長(zhǎng)度為1，直接返回對(duì)應(yīng)元素

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;

// 依次選取兩數(shù)組中較小的元素

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到其它點(diǎn)的最短距離

int distance[] = {n, 0, n, n, n, n};

// 每次從一點(diǎn)開(kāi)始搜索

boolean accessed[] = new boolean[node.length + 1];

// 共node.length個(gè)點(diǎn)

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的一個(gè)，易得起始節(jié)點(diǎn)到此點(diǎn)的距離已最小，可以開(kāi)始對(duì)其鄰居進(jìn)行訪問(wèn)

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);

// 寫(xiě)法1 匿名內(nèi)部類

Arrays.sort(stu, new Comparator() {

@Override

public int compare(Student o1, Student o2) {

if(o1.getScore() != o2.getScore())

return o2.getScore() - o1.getScore();

return o1.getAge() - o2.getAge();

}

});

// 寫(xiě)法2 lambda

Arrays.sort(stu, ((o1, o2) -> {

if(o1.getScore() != o2.getScore())

return o2.getScore() - o1.getScore();

return o1.getAge() - o2.getAge();

}));

// 寫(xiě)法3

Arrays.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) {

// 創(chuàng)建線程 將實(shí)現(xiàn)了Runnable接口的printer放入，start啟動(dòng)

Thread thread1 = new Thread(new Printer(), "線程1");

Thread thread2 = new Thread(new Printer(), "線程2");

thread1.start();

thread2.start();

}

static class Printer implements Runnable {

// 重寫(xiě)Run方法

@Override

public void run() {

while (true) {

// synchronized

synchronized (lock) {

// 打印完成

if (count > MAX) {

break;

}

System.out.println(Thread.currentThread().getName() + "打印數(shù)字: " + 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;

// 挑整數(shù)組位置，使得父節(jié)點(diǎn)大于子節(jié)點(diǎn)，從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始

for (int i = n / 2 - 1; i >= 0; i--) {

adjust(nums, n, i);

}

// 依次從堆中提取元素，

for (int i = n - 1; i > 0; i--) {

// 將當(dāng)前父節(jié)點(diǎn)移動(dòng)到末尾

int tmp = nums[0];

nums[0] = nums[i];

nums[i] = tmp;

// 移動(dòng)到末尾后繼續(xù)調(diào)整堆

adjust(nums, i, 0);

}

}

private static void adjust(int[] nums, int n, int i) {

// i表示父節(jié)點(diǎn)

int largest = i;

int left = 2 * i + 1; // 左子節(jié)點(diǎn)

int right = 2 * i + 2; // 右子節(jié)點(diǎn)

// 如果左子節(jié)點(diǎn)大于根節(jié)點(diǎn)

if (left < n && nums[left] > nums[largest]) {

largest = left;

}

// 如果右子節(jié)點(diǎn)大于當(dāng)前最大值

if (right < n && nums[right] > nums[largest]) {

largest = right;

}

// 如果最大值不是根節(jié)點(diǎn) 交換節(jié)點(diǎn)位置，使得較大一方到父節(jié)點(diǎn)位置

if (largest != i) {

int tmp = nums[i];

nums[i] = nums[largest];

nums[largest] = tmp;

// 調(diào)整交換后子節(jié)點(diǎn)所在的子樹(shù)

adjust(nums, n, largest);

}

}

}

柚子快報(bào)激活碼778899分享：手寫(xiě)一些常見(jiàn)算法

http://yzkb.51969.com/