冒泡和插入对比

一、比较次数

冒泡排序比较：

for (int i = 0; i < n; i++) {
    for (int j = n - 1; j > i; j--) {
        // 比较
        if (arr[j] < arr[j - 1]) {
            ...
        }
    }
}

插入排序比较:

for (int i = 1; i < n; i++) {
    int x = arr[i];
    int j = i;
    // 比较
    for (; j > 0 && x < arr[j - 1]; j--) {
        ...
    }
}

从比较次数上说，冒泡和插入的比较次数差不多，都是 O(n) 级别的。

二、交换次数

冒泡排序交换：

for (int i = 0; i < n; i++) {
    for (int j = n - 1; j > i; j--) {
        ...
        // 交换
        swap(arr, j, j - 1);
        ...
    }
}

插入排序比较:

for (int i = 1; i < n; i++) {
    int x = arr[i];
    int j = i;
    for (; j > 0 && x < arr[j - 1]; j--) {
        // 交换
        arr[j] = arr[j - 1];
    }
}

从交换次数上来说：

• 冒泡的交换（赋值）次数是 O(3n)：swap(arr, j, j - 1);
• 插入的交换（赋值）次数是 O(1n)：arr[j] = arr[j - 1];

理论上说，冒泡排序的交换次数是插入排序的 3 倍。

三、实验对比

使用数据测试冒泡排序和插入排序：

• 总共 10000 个数组
• 每个数组包含 [50, 250] 个元素

实验结果如下：

• 冒泡排序：348.1134 ms
• 插入排序：66.1865 ms

插入排序的性能是冒泡的好几倍。