算法精讲！带你轻松搞懂插入排序是咋回事

一. 引言

关于排序法算法其实有很多种，例如简单的有冒泡排序、选择排序，复杂一些的有快速排序、插入排序等，今天平哥就给大家讲解一下插入排序的实现过程。

二. 排序分析

插入排序，顾名思义就是每次排序时都是对插入的数据进行排列。例如，下面平哥给大家举个例子：

我们这里有一个数组，内部元素有3、1、5、2，如下图所示：

根据上图，我们可以总结出排序过程：

1. 第一轮比较，先拿前两个数进行比较，较大的放右边。3和1比较后，需要进行交换，变为了1、3；

2. 第二轮比较，插入元素5，与排好序的右边的数进行比较，也就是3和5比较。比较的结果是，新插入的值，比排好序的两个数中的最大值还要大，所以不用交换；

3. 第三轮比较，插入元素2，与排好的1、3、5进行比较。先从5开始，2比5小，将2和5交换；然后2再和前面的3比较，结果2比3小，继续交换；然后2再和前面的1比较，结果比1大，不用交换。最终我们确定排序的位置为：1-2-3-5。

通过以上这三轮的比较，我们可以得出一个结论：

4个元素进行比较，需要比较3轮 。 扩展来说，如果有n个元素，则需要比较n-1轮 。而 每一轮需要进行比较 的次数 ，最多每轮比较n-1次，且只要把 新 插入的数 ， 比已经排好 序 的最大数还要大，则直接退出 该 轮比较。

三. 代码实现

根据上面的理论描述，我们可以把上面的排序分析转换成行和列的排序过程，使用循环嵌套，利用如下代码进行实现插入排序：

public static void main(String[] args) {
    int[] a = { 3, 1, 5, 2 };
    
    for (int i = 0; i < a.length - 1; i++) { 
        //外层比较轮数
        for (int j = i; j >= 0; j--) { 
            //每轮次数比较，比较次数递增
            if (a[j + 1] < a[j]) {
               int t = a[j + 1];
               a[j + 1] = a[j];
               a[j] = t;
            } else { 
                //如果插入的数，排好序的最大值还要大，则退出该轮循环
                break;
            }
         }
    }
    
    System.out.println(Arrays.toString(a));
}

现在你知道利用Java怎么实现插入排序了吗？如果你还有其他问题，可以在评论区给平哥留言哦。当然，如果你想学习更多的算法知识，可以在B站上搜索千锋Java，我们有很多套免费的Java算法系列教程，欢迎免费订阅哦。