c - memmove 与复制单个数组元素

Question

在 CLRS 第 2 章中有一个练习，询问是否可以将插入排序的最坏情况运行时间改进为 O(n lg n)。我看到了this question发现做不到。

最坏情况下的复杂性无法改善，但与单独移动数组元素相比，使用 memmove 实际运行时间会更好吗？

单独移动元素的代码

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

使用 memmove

移动元素的代码

void insertion_sort(int arr[], int length)
{
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
                ;
        }
        if (k != j - 1){
            memmove(&arr[k + 2], &arr[k + 1], sizeof(int) *(j - k - 2));
        }
        arr[k + 1] = temp;
    }
}

我无法让第二个完美运行，但这是我正在考虑做的事情的一个例子。

使用 memmove 会不会有明显的速度提升？

Answer 1

memmove() 背后的实现可能在您的 C 库中得到了更优化。一些架构有指令可以非常有效地一次移动整个内存块。理论上的运行时复杂度不会得到改善，但它在现实生活中可能仍会运行得更快。