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

约定不等于承诺〃 2023-10-05 23:54 16阅读 0赞

#### 文章目录 ####

*  直接插入排序
 *   *  1. 特性
     *  2. 步骤
     *  3. 代码实现
     *  4. 稳定性

![9aabbfa419ff40abbd7f301f0534ecd7.png_pic_center][]

## 直接插入排序 ##

直接插入排序是一个比较简单的排序算法。作用是将一组数排序成升序的。  
  
![91f9e9bdc3134bfc8bcfa9bce99c525b.gif_pic_center][]

### 1. 特性 ###

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

### 2. 步骤 ###

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

![6cd801239fef420380ab611871a77d13.png_pic_center][]

直接插入排序就像是在打扑克牌一样，打牌的人会将有序的牌排在一起打出，在这里一组有序的数就相当于是顺子。  
  
  
  
1.定义一个 **i** 和 **j**，**i** 从1下标开始，而 **j** 是在 **i** 减1的位置，也就是在 **i** 的前面。  
![a3be6d3e2cdc48a2b71e969d8b074bef.png_pic_center][]  
  
  
2.定义一个 tmp 来存放当前 **i** 下标的值，比较 **j**，和 tmp 的值，如果 **j** 下标的值大于 tmp 的值，**j** 往左边走一次。  
![在这里插入图片描述][a045f3d2448a4606b53f8753ce9584de.png_pic_center]  
  
  
3. 当前 **j** 下标的值大于 tmp 的值， **j** 下标的值往右边走一次。  
![6166ed9187174534b546cecf78071194.png_pic_center][]  
  
  
4.**j** 变量往左走一次如果此时 **j** 此时小标位置小于0，则说明 **i** 左边的值都已经排序完成了。  
![a4a032eb617a496c9bbfc950a52acae7.png_pic_center][]  
  
  
5.将 tmp 的值放到 **j+1** 下标的位置，也就是当前的0下标。  
![a399b7b196874caf82449656016ad5c8.png_pic_center][]  
这就完成了一次插入排序，现在这组数就变成了 4 5 3 6 2。  
  
![4707ae466a38453ca9c12e7053655c76.gif_pic_center][]  
  
  
6.**i**\++，找到 **i** 下标的下一个位置。**j** 变量要始终指向 **i** 下标位置的前一个位置。（i - 1）  
![e2439da9bf7f429bb32ce793c0a82a5e.png_pic_center][]  
  
  
7.将此时 **i** 下标的值放到tmp中，比较 **j** 下标和tmp的值。  
![c8c81b452d8f4f198a07cef588fd7e8d.png_pic_center][]  
  
  
8. **j** 下标的值大于tmp的值，将 **j** 下标的值放到 **j** 后面的一个位置。

![8d122b357f454476b06192dfdadceef3.png_pic_center][]  
  
  
9.将 **j** 此时往左走一次，指向了0下标的位置。此时 **j** 下标的值大于tmp的值，将 **j** 下标的值往后走一个。  
![6aa28398cc894c859c746a0430430c51.png_pic_center][]  
  
  
10. **j** 此时往左走一次，指向了-1下标的位置。将tmp的值放到 **j** 下标之前的位置。

![fc8016bbde154b6c83fd38c74770fcb3.png_pic_center][]  
此时又排好了一个数据，排序剩下的数据步骤类似，这里就不 演示了。总之就是 **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;
            }
        }

### 4. 稳定性 ###

一个本身就稳定的排序，可以实现为不稳定的排序；但是一个本身就不稳定的排序，不能实现为稳定的排序。  
  
  
用下面的例子来演示直接插入排序的稳定性。

> 一、如果判断条件是 **j** 下标的值大于tmp的值。

![fecd0685fc9246aca55237e2b87ffc93.png_pic_center][]  
tmp中会存此时 **i** 下标的值，此时的 **j** 下标的值不大于tmp的值，tmp的值还会放到原来的位置。

1.  执行前：  
    ![6a40ebbc606e4da99158b4fb1ef2ff8a.png_pic_center][]
2.  执行后：

![9a156ecabfac49f8ac5c962a5f9d19d5.png_pic_center][]

可以发现排序完成后，两个数字5的顺序没有改变，此时是稳定的。

> 二、如果判断条件是 **j** 下标的值大于或者等于tmp的值

tmp中会存此时 **i** 下标的值，此时的 **j** 下标的值大于tmp的值，**i** 下标的值走到后面的一个位置，再将tmp的值放到此时 **j** \+1 下标的位置。  
  
![e0ed43de43fe49db95189effc2767804.png_pic_center][]  
可以发现排序完成后，两个数字5的顺序改变了，此时是不稳定的。

![513008b80edc4aeb93f1f76d3b319dca.gif_pic_center][]

[9aabbfa419ff40abbd7f301f0534ecd7.png_pic_center]: https://img-blog.csdnimg.cn/9aabbfa419ff40abbd7f301f0534ecd7.png#pic_center
[91f9e9bdc3134bfc8bcfa9bce99c525b.gif_pic_center]: https://img-blog.csdnimg.cn/91f9e9bdc3134bfc8bcfa9bce99c525b.gif#pic_center
[6cd801239fef420380ab611871a77d13.png_pic_center]: https://img-blog.csdnimg.cn/6cd801239fef420380ab611871a77d13.png#pic_center
[a3be6d3e2cdc48a2b71e969d8b074bef.png_pic_center]: https://img-blog.csdnimg.cn/a3be6d3e2cdc48a2b71e969d8b074bef.png#pic_center
[a045f3d2448a4606b53f8753ce9584de.png_pic_center]: https://img-blog.csdnimg.cn/a045f3d2448a4606b53f8753ce9584de.png#pic_center
[6166ed9187174534b546cecf78071194.png_pic_center]: https://img-blog.csdnimg.cn/6166ed9187174534b546cecf78071194.png#pic_center
[a4a032eb617a496c9bbfc950a52acae7.png_pic_center]: https://img-blog.csdnimg.cn/a4a032eb617a496c9bbfc950a52acae7.png#pic_center
[a399b7b196874caf82449656016ad5c8.png_pic_center]: https://img-blog.csdnimg.cn/a399b7b196874caf82449656016ad5c8.png#pic_center
[4707ae466a38453ca9c12e7053655c76.gif_pic_center]: https://img-blog.csdnimg.cn/4707ae466a38453ca9c12e7053655c76.gif#pic_center
[e2439da9bf7f429bb32ce793c0a82a5e.png_pic_center]: https://img-blog.csdnimg.cn/e2439da9bf7f429bb32ce793c0a82a5e.png#pic_center
[c8c81b452d8f4f198a07cef588fd7e8d.png_pic_center]: https://img-blog.csdnimg.cn/c8c81b452d8f4f198a07cef588fd7e8d.png#pic_center
[8d122b357f454476b06192dfdadceef3.png_pic_center]: https://img-blog.csdnimg.cn/8d122b357f454476b06192dfdadceef3.png#pic_center
[6aa28398cc894c859c746a0430430c51.png_pic_center]: https://img-blog.csdnimg.cn/6aa28398cc894c859c746a0430430c51.png#pic_center
[fc8016bbde154b6c83fd38c74770fcb3.png_pic_center]: https://img-blog.csdnimg.cn/fc8016bbde154b6c83fd38c74770fcb3.png#pic_center
[fecd0685fc9246aca55237e2b87ffc93.png_pic_center]: https://img-blog.csdnimg.cn/fecd0685fc9246aca55237e2b87ffc93.png#pic_center
[6a40ebbc606e4da99158b4fb1ef2ff8a.png_pic_center]: https://img-blog.csdnimg.cn/6a40ebbc606e4da99158b4fb1ef2ff8a.png#pic_center
[9a156ecabfac49f8ac5c962a5f9d19d5.png_pic_center]: https://img-blog.csdnimg.cn/9a156ecabfac49f8ac5c962a5f9d19d5.png#pic_center
[e0ed43de43fe49db95189effc2767804.png_pic_center]: https://img-blog.csdnimg.cn/e0ed43de43fe49db95189effc2767804.png#pic_center
[513008b80edc4aeb93f1f76d3b319dca.gif_pic_center]: https://img-blog.csdnimg.cn/513008b80edc4aeb93f1f76d3b319dca.gif#pic_center