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

Question

我已经使用固定长度数组实现了一个循环缓冲区。为了指向有效数据的开始，我使用了一个索引 (_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
}

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

Answer 1

如果你想做就地排序，那么你应该先压缩缓冲区。也就是说，使它成为从索引 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_index至 count-1 .或者，如果您真的希望缓冲区处于与之前相同的状态(只是重新排序的项目)，您可以使用我上面描述的相同类型的逻辑将内容移回原处。您为什么要这样做尚不清楚。