排序(六)直接插入排序

描述

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，总而得到一个新的，记录数增1的有序表。

将n个待排序的元素看成一个有序表和无序表，开始时有序表只有一个元素，无序表中有 n-1个元素，排序过程中每次去除无序表的一个元素，插入到有序表指定位置中，使之成为一个新的有序表，重复 n-1次可完成排序过程

流程

从第二个数开始循环，当循环数小于前面的数时，将循环数插入到小于数的位置，小于数到循环数的数组元素后移。

实例步骤 数组 ： 4 6 5 2

  1. 6 与前面的4 比较 。 发现6比4大 ，不执行后移

  2. 5 与前面得 4 6 比较 ， 发现比6小 ，将5插入到6的位置 ，然后6后移一位。

  3. 2与前面的 4 5 6 比较 发现比4小 ，将2插入到 4的 位置 然后 4 5 6 后移

得到 2 4 5 6

代码

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
/**
 * 将 j 插入到 i 的位置 ，且  i 到 j -1 的元素后移一位
 * @param a 数组
 * @param i 待插入的位置
 * @param j 插入的原位置
 */
public void insert(int[] a , int i , int j){
    int temp = a[j] ;
    //数组copy  参数意思从左往右  ： 原数组  ， 开始位置 ， 结果数组 
   //                     ， 目标数组的开始位置 ， 要复制的长度
    System.arraycopy(a, i, a, i + 1, j - i);
    a[i] = temp;
}


 /**
     * 直接插入排序
     * @param a
     */
    public void insertSort(int[] a ){
        for (int i = 1; i < a.length; i++) {
            //这种方式如果是反序的话 耗时少
            for (int j = 0; j < i; j++) {
                if (a[i] < a[j]){
                    insert(a , j , i);break;
                }
            }
            // 这种方式如果是正序的话 耗时少
//            for (int j = i-1 ; j > -1;j--){
////                if (a[j] < a[i]){
////                    insert(a , j + 1 , i);break;
////                }else if (j == 0){
////                    insert(a , j , i);break;
////                }
////            }
        }
    }

@Test
public void test(){
    int[] a = {5,4,7,1,6,9,2,8,3};
    insertSort(a);
    Arrays.stream(a).forEach(System.out::print);
}

引入哨兵后的优化 ：

哨兵的定义 ： 一切为简化边界条件而引入的附加节点【元素】均可称为哨兵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 直接插入排序 ， 引入 哨兵a[0] 所以a[0]不参加排序
 * @param a
 */
public void insertSortPlus(int[] a ){
    int i , j ;
    for ( i = 2; i < a.length; i++){
        if ( a[i] < a[i-1]){
            a[0] = a[i];
            for ( j = i -1; a[j] > a[0] ; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1 ] = a[0];
        }
    }
}

性能测试 ：发现我自己的那个排序是最快的， 而使用哨兵（insertSortPlus）并没有我那个（insertSort）快 . 如果在insertSortPlus 中不使用哨兵 ，儿时使用局部变量的话要比哨兵慢。

看代码吧 ， insertSort 和 insertSortPlus 的代码在前面。

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
/**
 * 直接插入排序
 * @param a
 */
public void insertSortPlusX(int[] a ){
    int i , j ,  temp  ;
    for ( i = 2; i < a.length; i++){
        if ( a[i] < a[i-1]){
            temp = a[i];
            for ( j = i -1; a[j] > a[0] ; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1 ] = temp;
        }
    }
}

@Test
public void test(){
    int[] a = new Random().ints(1,200000).limit(150000).toArray();
    int[] b = a.clone();
    int[] c = a.clone();
    long s = System.currentTimeMillis();
    insertSortPlus(a);
    long e = System.currentTimeMillis();
    System.out.println("plus耗时：" + (e - s));
    insertSort(b);
    long base = System.currentTimeMillis();
    System.out.println("普通耗时：" + (base - e));
    insertSortPlusX(c);
    long plusX = System.currentTimeMillis();
    System.out.println("plusX：" + (plusX - e));
    System.out.println();
}

image-20210226180704784

第三个输出的 PlusX , 对于这样的结果我很是惊讶 ， 我的猜想是insertSort归结于

System.arraycopy 这个方法的作用 。