50.【算法图解】

算法图解

(一)、二分查找O(log n)

1.使用二分查找的条件

二分查找目的是为了能够快速的遍历数据，然后能够得到我们想要的数据.查找的次数最多为:log2的n次方；相比原来的数据要减少很多复杂度.切记使用二分查找的前提是这个数据是有序的不能乱序，乱序就完蛋.

2.基本思路;

就是使目标值和中间值进行判断，假如说中间值大于目标值，那么就使hight=mid-1;如果中间值小于目标值那么就使low=mid+1;继续进行判断直到目标值和中间值相等为止.

3.代码展示:

import java.util.Scanner;publicclasshello{publicstaticvoidmain(String[] avgs){int[] arr_number =newint[50];
        Scanner sc =newScanner(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.*;publicclasshello{publicstaticvoidmain(String[] avgs){
        Scanner sc=newScanner(System.in);int[]arr=newint[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.*;publicclasshello{publicstaticvoidmain(String[] avgs){
        Scanner sc =newScanner(System.in);int[] arr =newint[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.*;publicclasshello{publicstaticvoidmain(String[] avgs){int[] arr ={1,5,2,6,8};InsertData(arr);}publicstaticvoidInsertData(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.*;publicclasshello{publicstaticvoidmain(String []avgs){long satrt=System.currentTimeMillis();//函数
        System.out.println("请您输入一个整数:");
        Scanner sc=newScanner(System.in);int number=sc.nextInt();
        System.out.println(number);long end=System.currentTimeMillis();float time=(float)(end-satrt)/1000;//函数
        System.out.println("运行时间是:"+time);}}

会有一定的误差，比较不适合推荐使用！！！！