一、算法思想

插入排序也是一种暴力（brute force）排序算法，它在每次迭代中将未排序的元素放在合适的位置。

插入排序的工作原理与我们在纸牌游戏中对手中的卡片进行排序类似。我们假设第一张卡片已经排序，然后我们选择一张未排序的卡片，如果未排序的卡片大于手中的卡片，则将其放在右侧，否则放在左侧，以同样的方式，其他未分类的卡片被取出并放在正确的位置。

1. 图解

假设我们试图按升序对元素进行排序。

二、工作流程

假设我们需要对以下数组进行排序。

假定数组中的第一个元素已排序，取第二个元素并将其单独存储在 key 中，将第一个元素

与 key 进行比较，如果第一个元素大于 key，则 key 放在第一个元素的前面。

现在前两个元素已排序，取第三个元素并将其与左侧的元素进行比较，并将它放在比它小的元素后面，如果没有小于它的元素，则将其放在数组的开头。

重复上面的步骤将每个未排序的元素放在正确的位置。

三、代码实现

1. 伪代码实现

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort
复制代码

2. java 实现

import java.util.Arrays;

/**
 * 插入排序
 *
 * @className: InsertSort
 * @date: 2021/6/24 17:07
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 4, 3};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        int length = arr.length;
        // 从第二个元素开始遍历
        for (int i = 1; i < length; i++) {
            // 定义一个指针指向第一个元素
            int j = i - 1;
            // 定义一个 key 保存下一个元素
            int key = arr[i];
            // 遍历 key 左边的每一个元素，直到找到比它小的元素
            while (j >= 0 && arr[j] > key) {
                // 将比 key 大的元素后移一位，留出空位存放 key
                arr[j + 1] = arr[j];
                j--;
            }
            // 将 key 放在比它小的元素的后面，也就是 arr[j] 的后面，完成此轮排序
            arr[j + 1] = key;
        }
    }
}
复制代码

四、排序复杂度

1. 时间复杂度

时间复杂度
最好	O(n)
最差	O(n²)
平均	O(n²)
空间复杂度	O(1)
稳定	是

最坏情况复杂度 O(n²)：假设一个数组按升序排列，而您想按降序对其进行排序。在这种情况下，出现最坏情况的复杂性。每个元素都必须与其他每个元素进行比较，因此，对于每个第 n 个元素，进行多次比较。因此，比较的总数 =O(n2)
最佳案例复杂度 O(n²)：当数组已经排序时，外循环运行n多次，而内循环根本不运行，只比较n次,因此复杂性是线性的。
平均案例复杂度 O(n²)：当数组的元素处于混乱的顺序（既不升也不降）时，就会发生这种情况。

选择排序的时间复杂度在所有情况下都是相同的，在每一步都必须找到最小元素并将其放在正确的位置。