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

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
}

通过使用上述方法，排序算法可以按顺序读取缓冲区，而不必意识到缓冲区由同一数组的两个非连续部分组成。

有没有更好的方法来对循环缓冲区进行排序？

- enzom83

---

你是否需要进行原地排序非常重要？你可以基于缓冲区生成一个IEnumerable<T>的数据，对其调用orderby方法，然后根据结果生成一个新的缓冲区吗？ - Servy

这实际上是排序还是旋转缓冲区，以使第一个元素位于基础数组的第一个元素位置？ - Ulrich Eckhardt

@Servy：缓冲区应包含要发送到网络中节点的消息。我该如何评估是否需要进行原地排序？ - enzom83

@UlrichEckhardt：这实际上是排序。 - enzom83

有什么特别的原因不能简单地重新排列元素，使它们从数组的位置0开始，并使用普通的排序算法吗？无论如何，对它们进行排序需要O(n log n)个元素移动，所以额外的O(n)不应该是一个问题... - Alexei Levenkov

@enzom83 如果你确实需要一个原地排序，你总可以按照我上面所描述的那样做，然后将所有值都复制回到缓冲区，但是你确定你真的需要一个原地排序吗？ - Servy

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' 到 'count-1' 的位置。 3. start_index > end_index: 数组中存在“空洞”（如您所示）。您需要将从 start_index 到数组末尾的项目移动到位置 array.length-start_index-count。

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

我应该指出，完成移动和排序后，您可以将 start_index 设置为 0，并将 end_index 设置为 count-1。或者，如果您真的想让缓冲区保持与之前相同的状态（只是重新排序了项），则可以使用我上面描述的相同逻辑将事物移回去。为什么要这样做还不清楚。

- Jim Mischel

---

+1. 从编码角度来看，显然最有效率，从性能角度来看和任何其他方法一样有效 - （重新排列块 + 排序）：O(n) + O(n log n)）仍然是 O(n log n)。 - Alexei Levenkov

Answer 2

简单的解决方案：

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

这个解决方案运行的时间是O(M)步来重新排列元素和O(MlogM)来对它们进行排序，总共需要O(MlogM)的时间。换句话说，将元素重新排列到缓冲区开头所需的时间与对它们进行排序所需的时间相比微不足道。

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

- Zoran Horvat

Answer 3

我建议实现一个修改版的快速排序算法。

快速排序是一种“分而治之”的算法，即将集合分成两部分，然后继续进行。您的缓冲区已经被分成了两部分，只需要进行调整。第一步是对两个部分进行排序，第一部分在数组开头，第二部分在数组结尾。您只需“预先排序”元素，以便第二部分中的每个元素都比第一部分中的任何部分都要小。然后您可以对每个部分应用快速排序算法，最终完成排序。

- user287107

---

+0: 我不明白你如何在实际排序之前进行“预排序” - 快速排序不能保证分区元素的位置。我认为可以在单独排序两个部分后使用归并排序作为后处理步骤。除非这是面试问题，否则不会这样做。 - Alexei Levenkov