java--冒泡排序、选择排序、二分查找、插入排序

桃扇骨 2022-05-15 17:39 254阅读 0赞

# 冒泡排序、选择排序、二分查找、插入排序 #

### 冒泡排序 ###

冒泡排序的思想就是两两比较，按从小到大输出的话，两个值相比，较小的放前大的放后，那么第一次两两比较结束后，最大值放在末尾，接下来再继续两两比较，但是这一次不需要比较到最后，因为最后已经是最大值了，所以每次两两比较结束后，都会少比一次，然后以此类推，直到数组中按从小到大排列。

###### 代码演示 ######

class Demo {
    public static void main(String[] args) {
                int[] a={22,11,4,33,5};
                //外循环是一共进行几轮比较的次数
                for(int i=0;i<a.length;i++){
      //内循环是两两比较一轮的次数，每一次两两比完后最大值都会放最后，因此都会少比一次
                    for(int j=0;j<a.length-1-i;j++){
                        if (a[j]>a[j+1]) {
                            int t=a[j];
                            a[j]=a[j+1];
                            a[j+1]=t;
                        }
                    }
                }
                //Arrays.toString()是打印数组，不需要遍历即可直接打印
                System.out.println(Arrays.toString(a));
        }
    }

结果

[4，5，11，22，33]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70]

### 选择排序 ###

选择排序的思想是取出一个元素，跟数组中的其他元素一一比较大小，按从小到大输出的话，取出的这个元素与数组中的其他元素进行比较，如果碰到比它小的元素就和它交换值，直到这个元素比完数组中的其他元素，这样第一轮比完最前的那个元素就是最小的，接下来会从第二个元素开始接着上述的过程，以此类推，直到数组中的元素按从小到大排列。

###### 代码演示 ######

class Demo {
    public static void main(String[] args) {
                int[] a={22,11,4,33,5};
                //外循环是一共进行几轮比较的次数
                for(int i=0;i<a.length-1;i++){
                //内循环是一轮比较的次数
                    for(int j=i+1;j<a.length;j++){
                        if (a[i]>a[j]) {
                            int t=a[i];
                            a[i]=a[j];
                            a[j]=t;
                        }
                    }
                }
                //Arrays.toString()是打印数组，不需要遍历即可直接打印
                System.out.println(Arrays.toString(a));
        }
    }

结果

[4，5，11，22，33]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1]

### 二分查找 ###

二分查找是在已经排好的数组里查询元素，并返回它的索引，它是先定义一个中间元素如果这个中间值大于你要查找的元素，你就往右边继续查找（反之则左边），在右边继续定义中间值，然后在继续照上述过程执行，直到搜索完所有元素。

import java.util.Scanner;
    class Demo {
        public static void main(String[] args) {
            int[] a = {22, 33, 44, 55, 66};
            //定义数组中最大的下标
            int max=a.length-1;
            //定义数组中最小的下标
            int min=0;
            /定义中间元素的下标
            int mid=(max+min)/2;
            Scanner x = new Scanner(System.in);
            System.out.println("请输入你要查找的数字：");
            int z=x.nextInt();
            //当mid取到两端值时，min和max就相当，因此循环条件就在min<=max
            while(min<=max){
            //如果要查询的元素刚好是中间元素时，退出循环
                if(z==a[mid]){
                    System.out.println("索引为："+mid);
                    break;
             //如果要查询的元素小于中间元素时，最大下标变为中间元素减1，中间元素重新计算
                }else if(z<a[mid]){
                    max=mid-1;
                    mid=(max+min)/2;
         //如果要查询的元素大于中间元素时，最小下标变为中间元素加1，中间元素重新计算           
                }else {
                    min=mid+1;
                    mid=(max+min)/2;
                }
            }
        }
    }

结果

请输入你要查找的数字：
    44
    索引为：2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 2]

### 插入排序 ###

插入排序就是在数组中先取出最开头的元素，然后把第二个元素和它比较，按从小到大输出的话，如果比他大就位置不变，反之则和它进行交换，接下来再继续取值，与前两进行比较，过程与上述一样执行，直到数组中的元素从小到大排列。

public class Insert {
        public static void main(String[] args) {
            int[] arr={5,2,7,3,1};
            //一共进行几轮比较的次数
            for (int i = 0; i < arr.length; i++) {
            //把i的值赋给j，这样在里面循环进行减1时，不会影响到外循环
                int j=i;
     //如果这个元素大于大于上一个元素，则进行交换，并且当前元素大于0，不然就没有前一个元素了
                while(j>0&&arr[j]>arr[j-1]){
                   int t=arr[j];
                   arr[j]=arr[j-1];
                   arr[j-1]=t;
     //当比较到第二轮以后元素会逐渐变多，为了能够再与前面的数据进行比较，就要在当前元素的下标减1
                   j--;
                }
            }
             //Arrays.toString()是打印数组，不需要遍历即可直接打印
            System.out.println(Arrays.toString(arr));
        }

结果

[7，5，3，2，1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70]: /images/20220503/f64409eda2ca4a2b9f795152a7e29142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1]: /images/20220503/04c104456a4b4d8699504e8a3d3a95d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 2]: /images/20220503/2c03f0a193a44f26b90330e269019a48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 3]: /images/20220503/33d63a29ed7b4aa098578f7b51cd6907.png