插入排序.

插入排序

插入排序法思想

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

插入排序的思路图解

代码实现

逐步推到的代码如下

package sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr={101,34,119,1,5};
        insertSort(arr);
    }

    //插入排序
    public static  void insertSort(int[] arr){
        //使用逐步推到的方式,便于理解
        //第一轮:{101,34,119,1}

        //定义待插入的数
        int insertVal=arr[1];
        int insertIndex=1-1;//定义一个带插入数的索引.即arr[1]的前面这个数的下标

        //给insertVal 找到插入的位置
        //说明,insertIndex>=0这句话说明在给insertVal找插入位置的时候不越界
        //insertVal
        //就需要将insertIndex往后移动
        while (insertIndex>=0&&insertVal<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]
            insertIndex--;
        }
        //当退出while循环时候,说明插入的位置找到,inserIndex+1
        arr[insertIndex+1]=insertVal;
        System.out.println("第一轮插入后:"+ Arrays.toString(arr));

        //第二轮带插入的数
         insertVal=arr[2];
         insertIndex=2-1;//定义一个带插入数的索引.即arr[1]的前面这个数的下标

        //给insertVal 找到插入的位置
        //说明,insertIndex>=2这句话说明在给insertVal找插入位置的时候不越界
        //insertVal
        //就需要将insertIndex往后移动
        while (insertIndex>=0&&insertVal<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]
            insertIndex--;
        }
        //当退出while循环时候,说明插入的位置找到,inserIndex+1
        arr[insertIndex+1]=insertVal;
        System.out.println("第二轮插入后:"+ Arrays.toString(arr));

    //第三轮代插入的数
    insertVal=arr[3];
    insertIndex=3-1;//定义一个带插入数的索引.即arr[1]的前面这个数的下标

    //给insertVal 找到插入的位置
    //说明,insertIndex>=3这句话说明在给insertVal找插入位置的时候不越界
    //insertVal
    //就需要将insertIndex往后移动
        while (insertIndex>=0&&insertVal<arr[insertIndex]){
        arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]
        insertIndex--;
    }
    //当退出while循环时候,说明插入的位置找到,inserIndex+1
    arr[insertIndex+1]=insertVal;
        System.out.println("第三轮插入后:"+ Arrays.toString(arr));

        //第四轮代插入的数
        insertVal=arr[4];
        insertIndex=4-1;//定义一个带插入数的索引.即arr[1]的前面这个数的下标

        //给insertVal 找到插入的位置
        //说明,insertIndex>=3这句话说明在给insertVal找插入位置的时候不越界
        //insertVal
        //就需要将insertIndex往后移动
        while (insertIndex>=0&&insertVal<arr[insertIndex]){
            arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]
            insertIndex--;
        }
        //当退出while循环时候,说明插入的位置找到,inserIndex+1
        arr[insertIndex+1]=insertVal;
        System.out.println("第四轮插入后:"+ Arrays.toString(arr));
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

insert Sorting

package sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr={101,34,119,1,5};
        insertSort(arr);
    }

    //插入排序
    public static  void insertSort(int[] arr){

        //使用for循环简化代码
        for(int i=1;i<arr.length;i++){
            int insertVal=arr[i];
            int insertIndex=i-1;//定义一个带插入数的索引.即arr[i]的前面这个数的下标

            //给insertVal 找到插入的位置
            //说明,insertIndex>=i-1这句话说明在给insertVal找插入位置的时候不越界
            //insertVal
            //就需要将insertIndex往后移动
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];//arr[insertIndex]
                insertIndex--;
            }
            //当退出while循环时候,说明插入的位置找到,inserIndex+1
            arr[insertIndex+1]=insertVal;
            System.out.println("第"+i+"轮插入后:"+ Arrays.toString(arr));

        }
}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

选择排序,我们就把上来的第一个数当成一个有序的,然后后面要插入的每一个数都是无序的,我们只要进行插入进行,只是在插入的过程中使用while进行循环,比较和位置的调换,同样我们上面做的是从小打到的排序,其实也是可以重大到小的,我们只需要把while循环中的**insertVal改为insertVal>arr[insertIndex]**即可.

希尔排序

这里我们引入一点希尔排序,其实希尔排序是对插入排序的优化,但是如何优化我们之后再说,但是希尔于插入排序有很密切的关联,然后这个我们既然说了插入排序,那么就把有关联的希尔排序说一说.
我们后面会说,对有序序列在插入时采用交互法的希尔排序和对有序序列在插入时采用移动法的希尔排序,这两种都用来希尔排序的核心,但是采用移动发我们里面还有插入排序的核心,同时采用移动发的希尔排序就是对简单插入法排序的代码的优化.