手写一些常见算法

news/2025/3/16 6:56:37/

手写一些常见算法

    • 快速排序
    • 归并排序
    • 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);}}
}

http://www.ppmy.cn/news/1579513.html

相关文章

C++中const与指针的使用详解

在 C++ 中,const 和指针的结合可以产生多种语义,主要涉及指针的指向关系和指向数据的可修改性。以下是常见的几种情况及其区别: 1. 指向常量的指针(Pointer to const) 语法:const T* ptr 或 T const* ptr 含义:指针指向的数据是常量,不能通过指针修改数据,但指针本身…

Manus 一码难求,MetaGPT、OpenManus、Camel AI 会是替代方案吗?

Manus 一码难求&#xff0c;MetaGPT、OpenManus、Camel AI 会是替代方案吗&#xff1f; 一、Manus 的现象与问题 Manus 作为一款号称“全球首个通用 AI 智能体”的产品&#xff0c;凭借其强大的功能和新颖的营销策略迅速走红。然而&#xff0c;其封闭的邀请码机制和高昂的使用…

[IP]UART

UART 是一个简易串口ip&#xff0c;用户及配置接口简单。 波特率从9600至2000000。 该 IP 支持以下特性&#xff1a; 异步串行通信&#xff1a;标准 UART 协议&#xff08;1 起始位&#xff0c;8 数据位&#xff0c;1 停止位&#xff0c;无奇偶校验&#xff09;。 参数化配置…

设计模式之美

UML建模 统一建模语言&#xff08;UML&#xff09;是用来设计软件的可视化建模语言。它的语言特点是简单 统一 图形化 能表达软件设计中的动态与静态信息。 UML的分类 动态结构图&#xff1a; 类图 对象图 组件图 部署图 动态行为图&#xff1a; 状态图 活动图 时序图 协作…

python Jsonpath表达式语法取值

python Jsonpath 语法规则&#xff1a; 演示数据&#xff1a;{"status":"0","msg":"成功","data": [ {"foo1": "bar1"},{"foo1": "bar2"}]} 根节点&#xff1a;$ $.status $.…

DAY33 贪心算法Ⅱ

122. 买卖股票的最佳时机 II - 力扣&#xff08;LeetCode&#xff09; 想到把整体利润分解为每天的利润&#xff0c;就豁然开朗了。 class Solution { public:int maxProfit(vector<int>& prices) {int result0;for(int i1;i<prices.size();i){resultmax(0,pric…

C#中,如何隐藏TextBox/RichTextBox中闪烁的光标?

方案&#xff1a;调用Windows API 1> 将TextBox的TabStop设置为false&#xff1b; 2> 在程序中相应位置加入下列代码 using System.Runtime.InteropServices; …… [DllImport("user32", EntryPoint "HideCaret")] private static extern bool…

Python在数据处理中的应用:从入门到精通

活动发起人小虚竹 想对你说&#xff1a; 这是一个以写作博客为目的的创作活动&#xff0c;旨在鼓励大学生博主们挖掘自己的创作潜能&#xff0c;展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴&#xff0c;那么&#xff0c;快来参加吧&#xff01…