我已经使用固定长度数组实现了一个循环缓冲区。为了指向有效数据的开始,我使用了一个索引 (_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)重载以对数组的那部分进行排序。
一旦确定要移动的内容和位置,您就可以通过一次操作移动项目。
分三种情况:
start_index == 0
: 不需要移动start_index < end_index
: 要移动的项目数是(end_index - start_index + 1)
.从start_index
移动项目通过end_index
到位置“0”到“count-1”start_index > end_index
:数组中有一个“洞”(如您所示)。您需要从start_index
移动项目通过数组的末尾到位置array.length - start_index - count
.
一旦确定了源位置和目标位置,就可以调用 Buffer.BlockCopy移动项目。
我应该注意,移动和排序完成后,您可以设置 start_index
到 0,和 end_index
至 count-1
.或者,如果您真的希望缓冲区处于与之前相同的状态(只是重新排序的项目),您可以使用我上面描述的相同类型的逻辑将内容移回原处。您为什么要这样做尚不清楚。
关于c# - 对循环缓冲区进行排序的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16573457/