插入排序
入门对部分有序的数组效率很高，是小型数据集的实际首选。
插入排序就像你手里抓了一把扑克牌，每次摸到新牌后，从右往左找到合适的位置把它插进去，手里的牌始终保持有序。
算法从第二张牌开始（第一张默认有序），逐张取出，和左边已排好的牌逐一比较，如果左边的牌更大就右移，直到找到正确的插入位置。
动画中可以关注"取出的牌"（key）和正在比较的位置，看它如何一步步找到正确的位置。
// 自定义输入
速度 中
待机 ⌨1void insertionSort(int arr[], int n) {
2 for (int i = 1; i < n; i++) {
3 int key = arr[i];
4 int j = i - 1;
5 while (j >= 0 && arr[j] > key) {
6 arr[j + 1] = arr[j];
7 j--;
8 }
9 arr[j + 1] = key;
10 }
11}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n)
最坏 O(n²)