说明

该分类下的内容只是个人笔记而已，放这里只是为了方便查找，算不上博客。

非专业定义

每次将一个待排序的元素，插入到前面已经排序的序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

其实就和你打扑克牌的时候把自己摸到手的牌从大到小排序一样一样的……

和打扑克牌的区别就是你不能凭空将一个元素放在两个元素之间,你得给他腾出一个位(元素后移)置来

排序过程示例

1
2
3
4
5
6
7
8
9
10
11
12
[1, 3, 1, 4, 2, 7, 6, 2, 1] # input
[1, 3, 1, 4, 2, 7, 6, 2, 1] # 1
[1, 1, 3, 4, 2, 7, 6, 2, 1] # 2
[1, 1, 3, 4, 2, 7, 6, 2, 1] # 3
[1, 1, 2, 3, 4, 7, 6, 2, 1] # 4
[1, 1, 2, 3, 4, 7, 6, 2, 1] # 5
[1, 1, 2, 3, 4, 6, 7, 2, 1] # 6
[1, 1, 2, 2, 3, 4, 6, 7, 1] # 7
[1, 1, 1, 2, 2, 3, 4, 6, 7] # 8
[1, 1, 1, 2, 2, 3, 4, 6, 7] # output

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void sort(int[] arr) {
  
  // 第0个元素认为是已经排好序的序列
  for (int i = 1; i < arr.length; i++) {
    int j = i;
    int tmp = arr[i];// 当前待插入到已经排好序的序列中的元素
    for (; j > 0 && tmp < arr[j - 1]; j--) { // 遍历前半部分已经排好序的序列
      arr[j] = arr[j - 1];// 后移
    }
    
    arr[j] = tmp; // 放到腾出来的位置
  }
  
}

特点

  • 平均时间复杂度 O(n^2)
  • 最差时间复杂度 O(n^2)
  • 空间复杂度 O(1)