排序算法 —— 直接插入排序（图文超详细）-Toy模板网

这篇具有很好参考价值的文章主要介绍了排序算法 —— 直接插入排序（图文超详细）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

直接插入排序

直接插入排序是一个比较简单的排序算法。作用是将一组数排序成升序的。

排序算法 —— 直接插入排序（图文超详细）

1. 特性

元素集合越接近有序，直接插入排序算法的时间效率越高。
时间复杂度：O(n^2)
空间复杂度：0(1)，它是一种稳定的排序算法。
稳定性：稳定

2. 步骤

下面以 5 4 3 6 2 这组数作为例子来讲解。

排序算法 —— 直接插入排序（图文超详细）

直接插入排序就像是在打扑克牌一样，打牌的人会将有序的牌排在一起打出，在这里一组有序的数就相当于是顺子。

1.定义一个 i 和 j，i 从1下标开始，而 j 是在 i 减1的位置，也就是在 i 的前面。
排序算法 —— 直接插入排序（图文超详细）

2.定义一个 tmp 来存放当前 i 下标的值，比较 j，和 tmp 的值，如果 j 下标的值大于 tmp 的值，j 往左边走一次。

3. 当前 j 下标的值大于 tmp 的值， j 下标的值往右边走一次。

4.j 变量往左走一次如果此时 j 此时小标位置小于0，则说明 i 左边的值都已经排序完成了。
排序算法 —— 直接插入排序（图文超详细）

5.将 tmp 的值放到 j+1 下标的位置，也就是当前的0下标。

这就完成了一次插入排序，现在这组数就变成了 4 5 3 6 2。

6.i++，找到 i 下标的下一个位置。j 变量要始终指向 i 下标位置的前一个位置。（i - 1）
排序算法 —— 直接插入排序（图文超详细）

7.将此时 i 下标的值放到tmp中，比较 j 下标和tmp的值。

8. j 下标的值大于tmp的值，将 j 下标的值放到 j 后面的一个位置。

排序算法 —— 直接插入排序（图文超详细）

9.将 j 此时往左走一次，指向了0下标的位置。此时 j 下标的值大于tmp的值，将 j 下标的值往后走一个。

10. j 此时往左走一次，指向了-1下标的位置。将tmp的值放到 j 下标之前的位置。

排序算法 —— 直接插入排序（图文超详细）
此时又排好了一个数据，排序剩下的数据步骤类似，这里就不演示了。总之就是 i 要一直++找到下一个数据，直到数组有序为止。

最终会排序成 2 3 4 5 6。

3. 代码实现

    //直接插入排序
    public static void insertSort(int[] array) {
        //i下标从数组的第二个值开始
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array[j + 1] = array[j];
                }else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                   break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array[j + 1] = tmp;
        }
    }