50.【算法图解】-Toy模板网

这篇具有很好参考价值的文章主要介绍了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);
    }
}