50.【算法图解】
算法图解
(一)、二分查找O(log n)
1.使用二分查找的条件
二分查找目的是为了能够快速的遍历数据,然后能够得到我们想要的数据.查找的次数最多为:log2的n次方;相比原来的数据要减少很多复杂度.切记使用二分查找的前提是这个数据是有序的不能乱序,乱序就完蛋.
2.基本思路;
就是使目标值和中间值进行判断,假如说中间值大于目标值,那么就使hight=mid-1;如果中间值小于目标值那么就使low=mid+1;继续进行判断直到目标值和中间值相等为止.
3.代码展示:
import java.util.Scanner; public class hello {
public static void main(String[] avgs) {
int[] arr_number = new int[50];
Scanner sc = new Scanner(System.in);
for (int i = 0,j=1; i < arr_number.length; i++,j++) {
arr_number[i] = j;
}
for (int i = 0; i < arr_number.length; i++) {
System.out.println(arr_number[i]);
}
int hight = arr_number.length - 1;
int low = 0;
int mid,idex=0;
System.out.println("请输入你要查找的数据是:");
int airNumber = sc.nextInt();
while (low <= hight) {
mid = (hight + low) / 2;
if (arr_number[mid] < airNumber) { //假如说中间值比目标值要小
low = mid + 1; //最低值为中间值+1;因为中间值已经计算过一遍了,再计算会增加
}
if (arr_number[mid] > airNumber) {
hight = mid - 1;
}
if (arr_number[mid] == airNumber) {
idex=mid;
break;
}
}
System.out.println("目标数字的坐标是:" + idex);
} }
4.时间复杂度是:O(log n);
(二)、冒泡排序(右)
1.什么是冒泡排序?
冒泡排序的英文Bubble Sort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。
2.冒泡排序原理:
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第 2 位上的数归位,依次类推下去。如果有 n 个数进行排序,只需将 n-1 个数归位,也就是要进行 n-1 趟操作。
而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。
3.冒泡排序的优缺点
根据复杂度的规则,去掉低阶项(也就是 n/2),并去掉常数系数,那复杂度就是 O(n^2)了;(高)
冒泡排序也是一种稳定排序,因为在两个数交换的时候,如果两个数相同,那么它们并不会因为算法中哪条语句相互交换位置。
4.代码展示:
import java.util.*;
public class hello {
public static void main(String[] avgs) {
Scanner sc=new Scanner(System.in);
int []arr=new int[5];
for(int i=0;i<arr.length;i++)
{
System.out.println("请您呼入第"+(i+1)+"个数子为:");
arr[i]=sc.nextInt();
}
for(int i=0;i< arr.length;i++)
{
for(int k=0;k<arr.length-1-i;k++) //排序到最右边
{
if(arr[k]>arr[k+1]) //进行交换
{
int temp;
temp=arr[k];
arr[k]=arr[k+1];
arr[k+1]=temp;
}
}
}
System.out.println("从小到大的排序是:");
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]);
}
}
}
5.时间复杂度为: O(n^2)
(三)、选择排序(左)
1.什么是选择排序?
选择排序是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(最大)的一个元素,存放在序列的开始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的后一个位置*。以此类推,直到全部待排序的数据元素排完。
2.选择排序原理
基本思想:每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止。
3.选择排序优缺点
选择排序是不稳定的排序方法。
4.代码展示:
import java.util.*;
public class hello {
public static void main(String[] avgs) {
Scanner sc = new Scanner(System.in);
int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
System.out.println("请您呼入第" + (i + 1) + "个数子为:");
arr[i] = sc.nextInt();
}
for (int i = 0; i < arr.length; i++) {
int min = i; //假设最小值的下标是:
for (int k = i + 1; k < arr.length; k++) {
if (arr[min] > arr[k]) {//假如说min大于k,那么两个人的坐标就要切换
min = k;
}
}
if (min != i) { //如果说最小值的坐标和最小值的坐标不相等,那么就把最小值的坐标放到最前面
int temp;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
System.out.println("从小到大的排序是:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
5.时间复杂度: O(n^2)
(四)、直接插入排序
1.什么是直接插入排序?
直接插入排序的定义就是:在一个已经排好的有序表中,从而得到一个新的,记录数增1的有序表
2.排序原理:
直接插入的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的。记录数增1的有序表。首先和右边的数字进行比较,假如满足条件,那么就设置一个临时数组,然后进行for循环,进行移动位置,直到不满足为止,然后进行交换.
3.代码展示:
import java.util.*;
public class hello {
public static void main(String[] avgs) {
int[] arr = {1, 5, 2, 6, 8};
InsertData(arr);
}
public static void InsertData(int[] arr) {
int temp; //设置临时空间
int j;
for (int i = 1; i < arr.length; i++) { //因为我们要从第二个判断是否有序啊
if (arr[i] < arr[i - 1]) {//假如说后一个小于前一个,那么就进入循环体
temp = arr[i]; //把后一个的空间腾出来
for (j = i - 1; j>=0&&temp < arr[j]; j--) { //假如说右边小于左边的,换位置
arr[j + 1] = arr[j];
}
arr[j + 1] = temp; //最后把最小的值放到后移后的位置
}
}
for(int k=0;k<arr.length;k++)//开始遍历
{
System.out.println(arr[k]);
}
}
}
4.时间复杂度为: O(n^2)
(五)、事前评估运行时间:
import java.util.*;
import java.awt.*;
public class hello {
public static void main(String []avgs)
{
long satrt=System.currentTimeMillis(); //函数
System.out.println("请您输入一个整数:");
Scanner sc=new Scanner(System.in);
int number=sc.nextInt();
System.out.println(number);
long end=System.currentTimeMillis();
float time=(float)(end-satrt)/1000; //函数
System.out.println("运行时间是:"+time);
}
}
会有一定的误差,比较不适合推荐使用!!!!
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击