gpt4 book ai didi

c# - 对循环缓冲区进行排序的最有效方法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:27:49 24 4
gpt4 key购买 nike

我已经使用固定长度数组实现了一个循环缓冲区。为了指向有效数据的开始,我使用了一个索引 (_startIndex)。同样,为了指向有效数据的结尾,我使用了另一个索引(_endIndex)。下面是一个例子。

  9   8   7   6   5   4   3   2   1   0   <-- array indices
3 2 1 0 5 4 <-- buffer indices
-----------------------------------------
| | | | | | | | | | |
-----------------------------------------
^ ^
_startIndex _endIndex

现在我需要重新排列这个缓冲区的元素:最小的元素应该移动到缓冲区的位置 0,而最大的元素应该移动到缓冲区的位置 5。

我的想法是基于以下方法。

int GetArrayIndex(int bufferIndex)
{
return (_startIndex + bufferIndex) % LENGTH;
// LENGTH is the length of the array
}

通过这种方式,排序算法可以使用上述方法顺序读取缓冲区,因此不必知道缓冲区由同一数组的两个不连续部分组成。是否有更好的方法对循环缓冲区进行排序?

最佳答案

如果你想做就地排序,那么你应该先压缩缓冲区。也就是说,使它成为从索引 0 到索引 5 的一个连续 block 。

然后你可以调用Array.Sort(T[], index, length)重载以对数组的那部分进行排序。

一旦确定要移动的内容和位置,您就可以通过一次操作移动项目。

分三种情况:

  1. start_index == 0 : 不需要移动

  2. start_index < end_index : 要移动的项目数是 (end_index - start_index + 1) .从 start_index 移动项目通过end_index到位置“0”到“count-1”

  3. start_index > end_index :数组中有一个“洞”(如您所示)。您需要从 start_index 移动项目通过数组的末尾到位置 array.length - start_index - count .

一旦确定了源位置和目标位置,就可以调用 Buffer.BlockCopy移动项目。

我应该注意,移动和排序完成后,您可以设置 start_index到 0,和 end_indexcount-1 .或者,如果您真的希望缓冲区处于与之前相同的状态(只是重新排序的项目),您可以使用我上面描述的相同类型的逻辑将内容移回原处。您为什么要这样做尚不清楚。

关于c# - 对循环缓冲区进行排序的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16573457/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com