排序“排序”数组

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而不是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堆存储数据，每次插入新的随机值后，在O(1)时间内删除min。

在n次迭代之后，执行n提取-min以获得排序列表。