2

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

这样，排序算法可以使用上述方法顺序读取缓冲区，而不必知道缓冲区由同一数组的两个不连续部分组成。有没有更好的方法来对循环缓冲区进行排序？

4

3 回答 3

7

如果要进行就地排序，则应首先压缩缓冲区。也就是说，使它成为一个从索引 0 到索引 5 的连续块。

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

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

有以下三种情况：

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

  2. start_index < end_index：要移动的项目数是(end_index - start_index + 1)。将项目从start_indexthrough移动end_index到位置 '0' 到 'count-1'

  3. start_index > end_index：数组中有一个“洞”（如您所示）。您需要将项目从start_index数组的末尾移动到 position array.length - start_index - count。

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

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

于 2013-05-15T19:48:25.340 回答
1

简单的解决方案：

  1. 移动元素，使值占据位置 0、1、...、M-1，其中 M 是数组中使用的位置数。
  2. 修改 _startIndex = 0 和 _endIndex = M-1
  3. 对 0 和 _endIndex 之间的部分缓冲区调用 Array.Sort （含）。

此解决方案以 O(M) 步骤运行以重新排列元素，并以 O(MlogM) 步骤对它们进行排序，总计 O(MlogM) 时间。换句话说 - 将元素重新排列到缓冲区开头所需的时间与对它们进行排序所需的时间相比可以忽略不计。

另一种解决方案是分别对缓冲区的第一部分和第二部分进行排序，然后将它们合并排序到数组的开头。运行时间相等（准确地说，稍微大一点），代码更复杂。

于 2013-05-15T19:53:11.077 回答
1

我建议实施修改后的快速排序。

快速排序是一种“分而治之”的算法，这意味着将集合分成两部分，然后继续。您的缓冲区已经分为两部分，只需要调整它们。第一步是对这两部分进行排序，第一部分在数组的开头，第二部分在数组的末尾。您只需“预排序”元素，以便第二部分中的每个元素都小于第一部分中的任何部分。然后你可以将快速排序算法应用于每一块，然后你就被排序了

于 2013-05-15T19:53:53.433 回答