排序循环缓冲区的最有效方法

Question

我使用固定长度的数组实现了一个循环缓冲区.为了指向有效数据的开始,我使用了index(_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的一个连续块.

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

一旦弄清楚要移动的内容,您可以通过一次操作移动项目.

有三种情况:

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

2. start_index < end_index:要移动的项目数(end_index - start_index + 1).从移动的物品start_index通过end_index通过对位置'0"计数1"

3. start_index > end_index:阵列中有一个"洞"(如图所示).您需要将项目从start_index数组末尾移动到位置array.length - start_index - count.

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

我应该注意,移动和排序完成后,您可以设置start_index为0,然后设置end_index为count-1.或者,如果你真的希望缓冲区处于之前的状态(只是重新排序的项目),你可以使用我上面描述的相同类型的逻辑来移动它.为什么你想这样做还不清楚.