新星计划Day11【数据结构与算法】 排序算法2

🛒导航小助手🎪

文章目录

• ​​新星计划Day11【数据结构与算法】 排序算法2​​
• ​​🛒导航小助手🎪​​

• ​​@[toc]​​

• ​​🤔55.冒泡排序算法代码实现​​
• ​​😫57.选择排序算法思路图解​​
• ​​🍠58.选择排序算法代码实现​​
• ​​🥖60.插入排序算法思路图解​​
• ​​🌮61.插入排序算法代码实现​​

🤔55.冒泡排序算法代码实现

public class BubbleSort{
    public static void main(String[] args){
        int arr[]={3,9,-1,10,-2};
         System.out.println("排序前");
         System.out.println(Arrays.toString(arr));
        //为了容量理解，我们把冒泡排序的演变过程，给大家展示
        //测试冒泡排序
        bubbleSort(arr);
        System.out.println("排序后");
         System.out.println(Arrays.toString(arr));
        //第一趟排序，就是将最大的数排在最后
        int temp=0;//临时变量
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1;j+=){
            //如果前面的数比后面的数大，则交换
            if(arr[j]>arr[j+1]){
                flag=true;
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        }
        System.out.println("第"+(i+1)+"趟排序后的数组");
        System.out.println(Arrays.toString(arr));
        if(!flag){//在一趟遍历中，一次交换都没有发生过
            break;
        }else{
            flag=false;//重置flag，进行下次判断
        }
        //第二趟排序，就是将第二大的数排在倒数第二位
          for(int j=0;j<arr.length-1-1;j+=){
            //如果前面的数比后面的数大，则交换
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        System.out.println("第二趟排序后的数组");
        System.out.println(Arrays.toString(arr));
        //第三趟排序，就是将第三大的数排在倒数第三位
          for(int j=0;j<arr.length-1-1-1;j+=){
            //如果前面的数比后面的数大，则交换
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        System.out.println("第三趟排序后的数组");
        System.out.println(Arrays.toString(arr));  
        //第四趟排序，就是将第四大的数排在倒数第四位
          for(int j=0;j<arr.length-4 ;j+=){
            //如果前面的数比后面的数大，则交换
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        System.out.println("第四趟排序后的数组");
        System.out.println(Arrays.toString(arr));  
    }
    //将前面的冒泡排序算法，封装成一个方法
    public static void bubbleSort(int[] arr){
        int temp=0;//临时变量
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1;j+=){
            //如果前面的数比后面的数大，则交换
            if(arr[j]>arr[j+1]){
                flag=true;
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        }
        //System.out.println("第"+(i+1)+"趟排序后的数组");
        //System.out.println(Arrays.toString(arr));
        if(!flag){//在一趟遍历中，一次交换都没有发生过
            break;
        }else{
            flag=false;//重置flag，进行下次判断
        }
    }
}      

😫57.选择排序算法思路图解

选择排序（select sorting）也是一种简单的排序方法。

它的基本思想是：

• 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换
• 第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换
• 第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换
• …
• 第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换
• …
• 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换
• 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

🍠58.选择排序算法代码实现

public class SelectSort{
    public static void main(String[] args){
        int[] arr={101,34,119,1};
        selectSort(arr);
    }
    //选择排序
    public static void selectSort(int[] arr){
        //使用逐步推导的方式来，讲解选择排序
        //第一轮
        //算法：先简单然后再做复杂
        for(int i=0;i<arr.length-1;i+1){
     
        int minIndex=i;
        int min=arr[i];
        for(int j=i+1;j<arr.length;j++){
            if(min>arr[j]){//说明假定的最小值，不是最小
                min=arr[j];//重置min
                minIndex=j;//重置minIndex
            }
        }
        }
        //将最小值，放在arr[0],即交换
        if(minIndex!=i){
        arr[minIndex]=arr[i];
        arr[i]=min;
        }
        System.out.println(Arrays.toString(arr));
        
        
       minIndex=1;
        min=arr[1];
        for(int j=1+1;j<arr.length;j++){
            if(min>arr[j]){//说明假定的最小值，不是最小
                min=arr[j];//重置min
                minIndex=j;//重置minIndex
            }
        }
        //将最小值，放在arr[0],即交换\
        if(minIndex!=1){
        arr[minIndex]=arr[1];
        arr[1]=min;
        }
        System.out.println(Arrays.toString(arr));
    }
}      

🥖60.插入排序算法思路图解

插入排序（Insertion Sorting）的基本思想是：

• 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
• 插入排序由于操作不尽相同，可分为 ​

  ​直接插入排序​

  ​​、​

  ​折半插入排序​

  ​​(又称二分插入排序)、​

  ​链表插入排序​

  ​​、​

  ​希尔排序​

  ​ 。

🌮61.插入排序算法代码实现

public class InsertSort{
    public static void main(String[] args){
        int[] arr={101,34,119,1};
        insertSort(arr);
    }
    public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            
      
        int insertVal=arr[1];
        int insertIndex=0;
        while(insertIndex>=0&&insertVal<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1]=insertVal;
        System.out.println(Arrays.toString(arr));
        }
    }
}