在数组内移动数组段

本文关键字：数组 移动 | 更新日期: 2023-09-27 18:16:04

如果我有一个项目数组:

1, 2, 3, 4, 5, 6, 7, 8

我想选择一组项目并将它们移动到数组中的另一个位置。例如:

1, 2, 5, 6, 7, 3, 4, 8

这里的5、6、7段被移到了索引2。

最有效的方法是什么，特别是限制额外的数组拷贝的数量。我有一个版本在工作，但它效率低下，在我的算法中形成了一个中心角色，我正试图优化它。

谢谢。

在数组内移动数组段

尝试使用链表。由于要移动列表的子部分，因此移动子列表两端的引用要比复制同一子列表中的每个单独项更节省内存。总的时间复杂度是相同的(Θ(n)遍历一个链表，Θ(n)复制一个数组段)，但是你会有更好的内存复杂度(常数n相对于Θ(n))和更少的连续内存分配/释放问题。

一种方法是切出应该移动的项，然后移动现有的成员:

// T[] source
// int dest
// int start, end
T[] slice = new T[end - start];
Array.Copy(source, start, slice, 0, slice.Length);
if (dest < start)
{
    // push towards end
    Array.Copy(source, dest, source, dest + slice.Length, start - dest);
}
else
{
    // push towards start
    // who moves where? Assumes dest..dest+count goes left
    Array.Copy(source, end, source, dest, dest - start);
}
Array.Copy(slice, 0, source, dest, slice.Length);

我知道你已经选好了答案;但是这个问题真的让我很恼火;看看能不能换一种写法

所以我写了这段代码: 
static int[] MoveSlice(int[] arr, int startIndex, int length, int newIndex)
{
    var delta = (int)Math.Abs(newIndex - startIndex);
    if (delta >= length)
    {
        for (var i = 0; i < length; i++)
        {
            var swap = arr[startIndex + i];
            arr[startIndex + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }
    }
    else
    {
        var newStart = newIndex + length;
        for (var i = 0; i < delta; i++)
        {
            var swap = arr[newStart + i];
            arr[newStart + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }
        var l = (int)Math.Abs(length - delta);
        arr = MoveSlice(arr, newIndex + delta, l, newIndex);
    }
    return arr;
}

我还没有测试性能。但我喜欢解决它!

也许您需要使用更多的代码来检查边界等可能的错误。

如果为了提高效率而想避免复制数组，可以完全避免。您可以使用单个值的最小变量来将项移动到它们的新目的地。这样的算法在内存上非常高效，而且总体上也是高效的，尽管它显然不能利用本机高效的数组复制。

相关文章：