插入排序是有问题的领域

Question

for(i = 1; i < len; i++){
    for(j = i - 1; j >= 0; --j){
        if(data[j] > data[1 + j]){
            swap(j, j + 1);
        } else {
            break;
        }
    }
}

swap 方法交换元素。为什么它应该是 --j 而不是 j-- ？有什么不同？放 j-- 有什么好处？

Answer 1

在这种情况下，两者都有效。

在 C++ 中有充分的理由使用 ++i。由于您使用 C 编写代码，因此请选择一个并坚持使用。

Answer 2

对于基本类型，后缀和前缀之间没有性能差异 increment/decrement。

顺便说一句，有更高效的插入排序算法实现，内循环中只有 1 个赋值（交换执行 3 个）。

int i, key, j;
for (i = 1; i < n; i++)
{
   key = arr[i];
   j = i-1;
   for (j = i-1; j >= 0 && arr[j] > key; --j) {
       arr[j+1] = arr[j];
   }
   arr[j+1] = key;
}

插入排序是有问题的领域

Insertion sorts's problamatic area

c

sorting

algorithm

performance

insertion-sort