插入排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 插入都是从未排序区间取出元素，插入到已排序区间合适的位置中
• 插入已排序区间时，同时要保证已排序区间的有序性

1.2 细节解释

比如说，数组 [2, 7, 1, 4, 3, 6, 5]。

首先分成未排序和已排序区间，第 1 个值无需排序，默认属于已排序区间：

已排序                           未排序
 ___                              ___ ___ ___ ___ ___ ___
| 2 |                            | 7 | 1 | 4 | 3 | 6 | 5 |

此时从未排序区间中取一个值 7，插入到已排序区间：

因为 7 > 2，所以 7 直接插入到 2 后面：

已排序                           未排序
 ___ ___                          ___ ___ ___ ___ ___
| 2 | 7 |                        | 1 | 4 | 3 | 6 | 5 |

继续从未排序区间取值 1，此时 1 < 7、1 < 2，所以插入到 2 前面：

已排序                           未排序
 ___ ___ ___                      ___ ___ ___ ___
| 1 | 2 | 7 |                    | 4 | 3 | 6 | 5 |

以此类推，后面每一步的结果如下：

插入 4：

已排序                           未排序
 ___ ___ ___ ___                  ___ ___ ___
| 1 | 2 | 4 | 7 |                | 3 | 6 | 5 |

插入 3：

已排序                           未排序
 ___ ___ ___ ___ ___              ___ ___
| 1 | 2 | 3 | 4 | 7 |            | 6 | 5 |

插入 6：

已排序                           未排序
 ___ ___ ___ ___ ___ ___          ___
| 1 | 2 | 3 | 4 | 6 | 7 |        | 5 |

插入 5：

已排序                           未排序
 ___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |

经过 n 轮插入以后，数组就排好序了。

二、算法实现

public void insertSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        // 未排序区间数据元素
        int x = arr[i];
        int j = i;
        // 插入到已排序区间合适的位置
        for (; j > 0 && x < arr[j - 1]; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = x;
    }
}

执行过程如下：

=====  初始数组 =====
[0, 3, 1, 6, 2, 5, 4]

=====第 1 轮插入=====
[0, 1, 3, 6, 2, 5, 4]

=====第 2 轮插入=====
[0, 1, 3, 6, 2, 5, 4]

=====第 3 轮插入=====
[0, 1, 2, 3, 6, 5, 4]

=====第 4 轮插入=====
[0, 1, 2, 3, 5, 6, 4]

=====第 5 轮插入=====
[0, 1, 2, 3, 4, 5, 6]

三、算法分析

3.1 时间复杂度

• 最好时间复杂度：O(n)
• 最坏时间复杂度：O(n^2)
• 平均时间复杂度：O(n^2)

3.2 空间复杂度

• 空间复杂度：O(1)
• 原地算法

3.3 稳定性

• 稳定排序算法

附录

/**
 * 插入排序
 * <p>
 * 时间复杂度：最好 O(n) 最差 O(n^2) 平均 O(n^2)
 * <p>
 * 空间复杂度：O(1)
 * <p>
 * 稳定性：稳定
 *
 * @author weijiaduo
 * @since 2022/7/21
 */
public class InsertSort implements Sort {

    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            // 未排序区间数据元素
            int x = arr[i];
            int j = i;
            // 插入到已排序区间合适的位置
            for (; j > 0 && x < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = x;
        }
    }

}