java二种排序和查找算法


目录

  冒泡排序

    思想

  冒泡排序优化

  选择排序

  优化选择排序

    思路

  线性查找

    思路

  二分查找(折半查找)

    思路

冒泡排序

思想:

外层循环控制遍历长度-1次,如n个数字比较n-1次 内层循环选取第一个数字开始,与后面的数字比较,如果比后面的数字小则进行交换 内层循环每次循环结束后的最后一个数字一定是最小的所有不用在参与下次循环,所以条件表达式可以减去i

package com.zll;
?
import java.util.Scanner;
?
public class bubbleSort {
   public static void main(String[] args) {
       /*动态获取数组元素:
       Scanner sc = new Scanner(System.in);
       System.out.println("请你输入6个数:");
       int[] arr=new int[6];
       for(int i=0;i            arr[i]=sc.nextInt();
       }*/
       int[] arr={2,5,6,4,1};
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
      }
       System.out.println()
       for(int i=0;i<arr.length-1;i++){
           for(int j=0;j<arr.length-i-1;j++){
               if(arr[j]<arr[j+1]){
                   int temp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=temp;
              }
          }
      }
       for (int i = 0; i < arr.length; i++) {
           System.out.print(arr[i]+" ");
      }
  }
}
?

冒泡排序优化

定义一个标志位,如果在内层循环中一次也没有进行交换就默认它已经是有序的了,就可以退出了。

for(int i=0;i<arr.length-1;i++){
          boolean flag=true;
           for(int j=0;j<arr.length-1-i;j++){
               if(arr[j]<arr[j+1]){
                   flag=false;
                   int temp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=temp;
              }
          }
           if(flag==true){
               break;
          }
      }
       System.out.println();
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
      }*

选择排序

package com.zll;
?
public class selectSort {
   public static void main(String[] args) {
       int[] arr={2,5,8,4,1};
for (int i = 0; i < arr.length - 1; i++) {
           for (int j = i; j <arr.length; j++) {
               if(arr[i]>arr[j]){
                   int temp=arr[i];
                   arr[i]=arr[j];
                   arr[j]=temp;
              }
          }
      }
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
      }
  }
}

以上方法交换次数太过频繁,有些元素可以不必要交换。所以可以用定义一个最大值下标,把元素与最大值下标进行比较。如下:

优化选择排序

思路

1.定义一个数组,把外层循环的变量的赋值为最大值的下标, 2.内层循环与最大值下标一一进行比较如果大于最大值下标的值,就把下标赋值给最大值max作为最大值的下标 3.内层循环结束后,得出第一趟最大值的下标j 4.退出第一次内层循环,并进行交换值,把得到的最大下标值与开始赋值第一个最大值进行交换 5.第二次外循环,最大值下标重新赋值为i,然后继续进行上述操作

package com.zll;
?
public class selectSort {
   public static void main(String[] args) {
       int[] arr={2,5,8,4,1};
  for (int i = 0; i < arr.length; i++) {
           int max=i;
           for (int j = i; j < arr.length; j++) {
               if(arr[j]>arr[max]){
                   max=j;
              }
          }
           if(max!=i){
               int temp=arr[i];
               arr[i]=arr[max];
               arr[max]=temp;
          }
      }
       for(int i=0;i<arr.length;i++){
           System.out.print(arr[i]+" ");
      }
  }
}
?

线性查找

思路

线性查找,采用逐一比对的方式对数组进行遍历 查找你所输入数的下标

package com.zll;
?
import java.util.Scanner;
?
public class seqSearch {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.println("请输入数字");
       int num=sc.nextInt();
       int[] arr={3, 8, 1, 5, 2, 7, 4, 6, 9};
       for(int i=0;i<arr.length;i++){
           if(arr[i]==num){
               System.out.println(i);
          }
      }
  }
}
?

二分查找(折半查找)

思路

定义三个变量分别存储,最小下标数,最大下标数,和中间下标数 把要查找的数与中间下标数的值对比如果小于中间下标值,就把中间下标减一作为要搜寻范围的最大值 如果大于中间值就在右边搜寻把中间下标值+1作为范围的最小值开始循环

package com.zll;
?
import java.lang.reflect.WildcardType;
import java.util.Arrays;
?
public class binarySearch {
  public static void main(String[] args) {
      int num=10;
      int[] arr={1,2,3,4,5,6,7,8,9,13};
      System.out.println(Arrays.toString(arr));//可以使用Arrays函数进行输出数组
      int max=arr.length-1;
      int min=0;
      while (true){
          int mid=(max+min)/2;//mid中间下标
          if(num>arr[mid]){
              min=mid+1;
          }else if(num               max=mid-1;
          }else {
              System.out.println(mid);//找到了这个数的下标,进行输出
              break;
          }
          if(max               System.out.println("此元素不存在");
              break;
          }
      }
  }
}
?