就像打牌时理牌一样——手里的牌已经排好了，新摸一张牌，找准位置插进去就行。
想象打扑克牌时理牌的过程：手里已经有几张牌，按大小排好了；每摸到一张新牌，不需要把手里的牌全部重新排一遍——只需要从后往前找，把新牌插进合适的位置就行，前面已经排好的牌之间的顺序完全不受影响。
插入排序就是把这个过程搬到数组上：把数组分成"前面已经排好的部分"和"后面还没处理的部分"，每次从"还没处理"里取出第一个数，往"已经排好"的部分里找到该插入的位置，插进去——重复这个动作，直到所有数都插入完毕。
同样用 {5, 2, 8, 1, 9} 演示。一开始只把第一个数（5）看作"已经排好"的部分（一张牌当然算排好了），从第二个数开始，一个个往前插：
| 1 | void InsertionSort(int arr[], int n) |
| 2 | { |
| 3 | for (int i = 1; i < n; i++) // 从第2个数开始，逐个取出来插 |
| 4 | { |
| 5 | int current = arr[i]; // 取出当前这张"新牌" |
| 6 | int j = i - 1; // 从已排好部分的最后一个开始往前找 |
| 7 | while (j >= 0 && arr[j] > current) |
| 8 | { |
| 9 | arr[j + 1] = arr[j]; // 比current大，往后挪一位腾位置 |
| 10 | j--; |
| 11 | } |
| 12 | arr[j + 1] = current; // 腾出的空位正好插入current |
| 13 | } |
| 14 | } |
i=3 取出 1 时，前面三个数都比它大，要连续挪三次才能腾出最前面的位置——插入排序"挪的次数"取决于新数要往前插多远，越靠前插，挪的次数越多。看上面的例子能发现一个规律：如果新数比"已排好部分"的最后一个还大，连一次都不用挪（就像 i=2 和 i=4 那样，while 循环条件一开始就不满足）。这意味着，如果原数组本来就已经接近排好序，插入排序几乎不需要挪动任何数据，速度会非常快。
10 个数总共只要 9 次比较，完全不需要移动，是 O(n)；如果数组完全逆序，每个新数都要插到最前面，比较和移动次数都暴涨到 45 次（也就是 n(n-1)/2），变成了 O(n²)。两种情况的差距非常悬殊。| 情况 | 比较/移动次数 | 时间复杂度 |
|---|---|---|
| 最好情况（已经排好序） | 约 n 次，0 次移动 | O(n) |
| 最坏情况（完全逆序） | 约 n²/2 次 | O(n²) |