八大排序(三)之插入排序

插入排序

 基本思想:
 1.把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表只包含一个元素,无序表中包含n-1个元素,
 2.排序过程中每次从无序表中取出第一个元素,她的排序码依次与有序表的排序码进行比较
 3.将它插入到有序表中的适当位置,使之成为新的有序表。

首先写一个插入排序方法

  public  static void insertSort(int [] arr){
        for (int i = 1; i <arr.length ; i++) {
            //定义待插入的数
            int insertVal=arr[i];
            int insertIndex=i-1;//即arr[i]前面这个数的下标
            /*
            * 1.insertIndex>=0 保证在给insertVal找到插入位置,不越界
            * 2.insertVal<arr[insertIndex]待插入的数,还没有找到插入的位置
            * 3.就需要将arr[insertIndex]后移*/
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];//将arr[insertIndex]向后移一位
                insertIndex--;
            }
            /*退出while循环说明找到了插入的位置,insertIndex+1*/
            arr[insertIndex+1]=insertVal;
            count++;
            System.out.printf("第%d轮"+Arrays.toString(arr)+"\n",count);
        }
    }

然后测试

  public static void main(String[] args) {
          int [] arr={4,2,5,6,1};
          System.out.println("排序前"+Arrays.toString(arr));
          insertSort(arr);
    }

最后是结果图

八大排序(三)之插入排序

上一篇:排序算法-插入排序


下一篇:学习笔记-插入排序