排序-直接插入

今天记录下关于：直接插入排序一些理解和心得。
主要分为以下几个方面分享

• 直接插入排序的思想
• 实现方式
• 时间复杂度

---

直接插入排序的思想

当前位置:

1:当前位置是从下标为“1”处开始的。之所以不从0开始是因为，0前边至0位置的数只有array[0]，就它自己肯定是已经排好序的。所以只需要从1处开始。
2:每次循环递增“+1”。

排序思想：

定义:将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数量增1的有序表。
理解:
1:给定一个具有n位数据的数组，从 当前位置开始 至 1位置，依次与 前一位 进行 两两比较，如果当前值小(大)则交换2者的值。
2:重复n-1次上述操作，直至该序列中所有数据满足降(升)序为止。

---

实现方式

    public static void main(String[] args){
        Integer[] array = Util.createRandomArray(100, 10);
        Integer[] array2 = Arrays.copyOf(array, array.length);
        Integer[] array3 = Arrays.copyOf(array, array.length);

        System.out.println("Arrays:" + Arrays.toString(array) + "------------------------------------");

        insertSort2(array2);
        Util.print(array2, "InsertSort2");

        System.out.println("------------------------------------");

        Util.test(array3);
        Util.print(array3, "对数器");
    }

    private static void insertSort2(Integer[] source){
        Util.checkSrc(source);

        for(int i = 1; i < source.length; i++){  //n-1次循环
            for(int j = i; j >= 1; j--){         //swap循环。记录当前位置
                if(source[j] < source[j -1]){    //如果当前位置比前一位要小,则执行swap操作。
                    int temp = source[j - 1];
                    source[j - 1] = source[j];
                    source[j] = temp;
                }
            }
        }
    }

log:

Arrays:[45, 99, 39, 93, 71, 92, 68, 34, 91, 59]-----------------
InsertSort2:34---39---45---59---68---71---91---92---93---99
----------------------------------------------------------------
对数器:34---39---45---59---68---71---91---92---93---99

---

时间复杂度

时间复杂度:
结论:O(n^2)
分析:假如有n=5个数要排序，总共需要执行n-1=4次循环操作
第1次：需要比较 1次
第2次：需要比较 2次
第3次：需要比较 3次
第4次：需要比较 4次

总共执行的次数为：1 + 2 + ... + n-2 + n-1===>n^2/2，所以该排序的时间复杂度为:O(n^2)
 
空间复杂度:
1:O(1)
2:不需要额外申请内存