直接插入排序是Java的八大排序算法之一，顾名思义，就是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表的排序算法。直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。直接插入排序算是我们目前接触过的最简单的一种排序算法了。

1.算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

①. 从第一个元素开始，该元素可以认为已经被排序

②. 取出下一个元素，在已经排序的元素序列中从后向前扫描

③. 如果该元素（已排序）大于新元素，将该元素移到下一位置

④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤. 将新元素插入到该位置后

⑥. 重复步骤②~⑤

2.代码实现

提供两种写法，一种是移位法，一种是交换法。移位法是完全按照以上算法描述实，再插入过程中将有序序列中比待插入数字大的数据向后移动，由于移动时会覆盖待插入数据，所以需要额外的临时变量保存待插入数据，代码实现如下：

①. 移位法：

public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int temp = a[i]; // 先取出待插入数据保存，因为向后移位过程中会把覆盖掉待插入数
            while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大，就后移
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp; // 找到比待插入数据小的位置，将待插入数据插入
        }
    }

而交换法不需求额外的保存待插入数据，通过不停的向前交换带插入数据，类似冒泡法，直到找到比它小的值，也就是待插入数据找到了自己的位置。
②. 交换法：

  public static void sort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 1; i < arr.length; i ++) {
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[i]) {
                arr[j + 1] = arr[j] + arr[j+1];      //只要大就交换操作
                arr[j] = arr[j + 1] - arr[j];
                arr[j + 1] = arr[j + 1] - arr[j];
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

3.算法效率

直接插入排序不是稳定的排序算法。

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n2)	O(n)	O(n2)	O(1)

直接插入排序作为最简单的排序算法，很容易理解，我们看完了本文基本上就能掌握，但在Java中还要很多的复杂的算法需要我们花费大量的时间和精力去学习，这时候一个好的学习资源显得尤为重要，动力节点在线就是这样一家为我们提供优质Java学习资源的免费学习网站，快快收藏起来吧！