Java干货分享：直接插入排序

上一期里知了堂小编给大家分享了选择排序，今天小编接着给大家安利另一个排序算法——直接插入排序。

直接插入排序和它的字面意思一样，将数字插入到有序序列中排序。咱们还是借用上期小朋友按身高排序的例子来理解：一排小朋友身高不同，我们需要将小朋友们按照从矮到高的规则排成一排，这时候我们选择当前这一排中第一个小朋友，将他作为新顺序的第一个。接下来将无序序列中的第二个小朋友与之前的小朋友比较身高，如果低就作为新顺序的第一个，如果高就作为新顺序的第二个。

现在我们再来带入直接插入排序，我们的数据就和小朋友们的身高一样按照从小到大排序：首先我们进入循环，将第一个数字添加到新序列的第一位，之后遍历到的数字都与新序列的每一个数字进行大小比较，插入到合适的位置。当遍历完成之后，新的序列也就排出来了。

在直接插入排序中，需要进行两个循环嵌套，接下来还是用图文逻辑给大家演示直接插入排序的流程。

第一趟：（1）将第一个数11作为新有序序列的第一个数，其他数暂时不做处理，得到结果为下图。

第二趟：（1）循环来到第二个数5，将5与有序序列的数字进行大小比较；（2）5<11，将11后移一位，5插在11前，此时得到结果为下图：

第三趟：（1）此时大循环来到原始序列第三个数8，将8与有序序列的每个数进行比较；（2）8>5，此时5的位置不变，将8与11比较；（3）8<11，11后移一位，8插入11与5之间，此时得到结果如下：

第四趟：（1）循环到原始序列第4个数20，将20与新序列进行比较；（2）20>5，5的位置不变；（2）20>8，8的位置不变；（3）20>11，此时11的位置不变，20插入在有序序列最后一位。得到结果如下图：

第5趟：（1）此时大循环来到原始序列最后一位数17，进入小循环与有序序列进行比较大小；（2）17>5，17>8，17>11，17<20，此时5、8、11都小于17位置不变，17小于20，因此20向后移一位，17插入在20前一位。此时原始序列已经循环完成，最终得到的序列就是我们需要的排好顺序的序列，最终结果如下：

小编同样为大家准备了动图理理思路。

看完直接插入排序的逻辑和原理之后，小伙伴们明白是怎么一回事了吗？下面小编给大家准备了Java实现直接插入排序的代码，自己动手试试吧！

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

那么今天的分享就到这里了，想获取更多Java干货和行业知识，扫码关注知了汇智。