2

我试图理解以下锦标赛排序（替换选择），它是一种用于在主存储器中进行排序的排序算法。

任何解释这是如何工作的？

Keep two heaps in memory, H1 and H2
read B-2 pages of records, inserting into H1;  #B is buffer size

while (records left) {
  m = H1.removemin();  
  put m in output buffer;
  if (H1 NOT empty)
       read in a new record r (use 1 buffer for input pages);
       if (r < m)  
           H2.insert(r);
       else        
           H1.insert(r);
 else
      H1 = H2;  
      H2.reset();  
      start new output run; 
}
H1.output();  
start new run;  
H2.output();
4

1 回答 1

1

替换选择技术特别有趣，因为产生的运行的预期长度是可用主存储器大小的两倍。这种估计首先由 EH Friend 在 EF Moore 中提出，后来由 EF Moore 描述。在现实世界的应用中，输入数据通常不是随机的（即，它经常表现出某种程度的预排序）。在这种情况下，由替换选择生成的运行往往包含超过 2m 条记录。事实上，对于最好的情况，即当输入数据已经排序时，替换选择只产生一次运行。

给定一组元组记录 status ，其中 record 是从未排序的输入读取的记录， status 是一个布尔标志，指示该记录是活动的还是非活动的。活动记录是当前运行的候选记录，而非活动记录则保存以供下次运行。该算法背后的思想如下：假设主存储器大小为 m，我们从未排序的输入数据中读取 m 条记录，将其状态设置为活动。然后，选择具有最小键和活动状态的元组并将其移动到输出文件。当一个元组被移动到输出（选择）时，它的位置被输入数据中的另一个元组占据（替换）。如果最近读取的记录小于刚刚写入的记录，则其状态设置为非活动，这意味着它将被写入到下一次运行。一旦所有元组都处于非活动状态，

您可以在此处阅读有关替换选择的更多信息。

于 2015-04-24T13:12:29.150 回答