对"已排序"数组进行排序

Question

1. 假设给定一个大小为n的数组,其中包含有序值.
2. 在迭代i中,给出一个新的随机生成的值,并将其插入到数组的末尾.
3. 然后使用该数组,并丢弃最小值项.
4. 在迭代n之后,保留的数组将包含最大值项.

例如,在Java语法中,它将类似于:

List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

但它似乎效率低下.有更好的算法吗？

Answer 1

使用二进制插入(类似二进制搜索)作为新值.丢弃最小的.应该很快.

顺便说一句 - 这可以作为一个方便的扩展方法实现:

private static int GetSortedIndex( this IList list, IComparer comparer, object item, int startIndex, int endIndex )
{
  if( startIndex > endIndex )
  {
    return startIndex;
  }
  var midIndex = startIndex + ( endIndex - startIndex ) / 2;
  return comparer.Compare( list[midIndex], item ) < 0 ?
    GetSortedIndex( list, comparer, item, midIndex + 1, endIndex ) :
    GetSortedIndex( list, comparer, item, startIndex, midIndex - 1 );
}

public static void InsertSorted( this IList list, IComparer comparer, object item )
{
  list.Insert( list.GetSortedIndex( comparer, item ), item );
}

Java等效

public static void main(String[] args)
{
   List l = new ArrayList();
   l.add(new Integer(2));
   l.add(new Integer(3));
   l.add(new Integer(6));
   l.add(new Integer(9));

   Random rand = new Random();
   for (int i=0; i < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

Answer 2

使用TreeSet代替a List,它将维护顺序,使得最大值始终位于SortedSet#last().如果使用1.6+,您可以使用NavigableSet方法; pollLast()将返回并删除最高值.

NavigableSet<Integer> set = new TreeSet<Integer>();

//... setup data

Integer highest = set.pollLast();

set.add(rand.nextInt(1000));

Integer newHighest = set.pollLast();

Answer 3

使用min-heap存储数据,并在每次插入新的随机值后,在O(1)时间内删除min.

在n次迭代之后,执行n extract-min以获得排序列表.

Answer 4

我很惊讶没有人提到过这个...你正在寻找的数据结构是一个优先级队列.毫无疑问,这是完成此任务的最有效方式.可以使用许多不同的方法实现优先级队列(请参阅链接的文章),但最常见的是基于二进制堆.在自我二元变换(这是非常典型的)中,插入和删除都需要O(log n)时间.

Java库中似乎有一个内置的泛型类PriorityQueue<E>,所以看起来你可以直接使用它.这种类型似乎并不令人惊讶地基于堆数据结构,尽管比我不能说的更具体.无论如何,它应该非常适合您的使用.