java - 插入/排序到循环优先级队列的算法

Question

// gives next index in array which wraps around in a ring; moves clockwise through indices 
private int nextSlot(int k) { 
  return ((k + 1) % A.length); 
} 

// Insert method
public void insert(int k) {
   if( size == A.length)
       resize();
   A[next] = k;
   for(int i = 0; i < next; i = nextSlot(i)) {
       if(k < A[i]) {
           for( int j = next - 1; j >= i; j--){
               A[nextSlot(j)] = A[j];
           }
           A[i] = k;
           break;
       }
   }
   next = nextSlot(next);
   size++;
} 

我正在尝试创建一个插入/排序方法，以升序将值插入循环优先级队列。我遇到的问题是当下一个指针循环回到数组的开头时，队列前面的项目没有被排序。我已经为此苦苦挣扎了几个小时，我们将不胜感激任何帮助。

Answer 1

具体来说，当 next 循环回到开头时，它将为 0，因此这个 for 循环:

for(int i = 0; i < next; i = nextSlot(i)) {

不会做任何事。

但是，总的来说，我发现您的程序存在一些问题。首先，为什么要将其实现为圆形数组？当您希望能够从数组的开头和结尾快速添加/删除时，循环数组很有用。您似乎要插入到中间，因此无论如何在每次插入时对整个列表进行线性搜索时，没有理由使代码复杂化。

最后，请注意，在对圆形数组进行操作时，您需要考虑到您的索引会环绕并变为 0。因此，这一行:

for( int j = next - 1; j >= i; j--)

至少有两个原因是错误的:

1. j>=i 不是判断 j 是否达到 i 的正确方法
2. j-- 也是错误的，因为 j-1 需要包装