memmove与复制单个数组元素

Question

在CLRS第2章中,有一个练习,询问是否将插入类型的最坏情况运行时间改进为O(n lg n).我看到了这个问题,发现它无法完成.

最坏情况下的复杂性无法改善,但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库中进行更优化.一些架构具有非常有效地一次移动整个存储器块的指令.理论运行时间的复杂性不会得到改善,但在现实生活中它可能仍会运行得更快.