插入排序的优势

插入排序有个别人比不了的优点：当数据本来就基本有序时，它几乎不用挪动。因为每张"新牌"往前一比，发现前面的都比它小，立刻就停下了。就像整理一副已经排好、只有一两张插错的牌，你扫一眼就理顺了。

#include <iostream>
using namespace std;
int main() {
    int a[6] = {1, 2, 3, 4, 6, 5}, n = 6;   // 只有最后两个乱
    long moves = 0;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; moves++; }
        a[j + 1] = key;
    }
    cout << "一共挪动了 " << moves << " 次";  // 只挪动 1 次
}

对基本有序的数据，插入排序接近 $O(n)$，非常快。别被"它平均慢"这句话误导——要看数据长什么样。