排序问题-一遍算法 [英] Sorting question -- One pass algo

问题描述

排序问题-一遍算法
给定n个排序的整数列表作为文件输入，编写一种单次通过算法，生成一个排序的输出文件，其中输出是n个输入文件的排序合并.

我当时在考虑使用Merge sort，但是它的复杂度是O(nlogn).
你们有什么建议?
如何在n个排序的整数列表上应用一遍算法?
提出一些可以让我起步的策略.

Sorting question -- One pass algo
Given n sorted lists of integers as file input, write a one-pass algorithm that produces one sorted file of output, where the output is the sorted merger of the n input files.

I was thinking of using Merge sort , but its complexity is O(nlogn).
What do you guys suggest?
How can I apply one-pass algo on n sorted list of integers??
Suggest some strategy that will give me a kick to start.

推荐答案

将n个排序的整数列表作为文件输入"

对我来说，这意味着对输入进行排序，因此这是优化输出的一种情况.沿着这条线的某个地方会很脏:

每个文件的

"Given n sorted lists of integers as file input"

To me this means that the inputs are sorted, so it''s a case of optimising the output. Somewhere along this line will do the dirty:

for each file
  read the first number into a sorted list
end loop
while the list is non empty and the files have more items
  write the first item in the sorted list to the output
  if the item's file has more
    read next item from file into sorted list
  end if
end loop

您只需要记录每个项目来自哪个文件，并有一个可以将项目添加到其中的排序列表.
我将把实现留作OP的练习.

You simply need to record which file each item comes from and have a sorted list that the items can be added into.
I will leave the implementation as an exercise for OP.

在这里查看本文 TimSort

1.像这样初始化算法:

1. Initialize the algorithm like that:

read the first number from each file
sort the files by those numbers, lowest first

2.主要算法应如下所示:

2. The main algorithm should work like this:

while (file list not empty)
{
  do
  {
    store the number from the first file
    get the next number from that file
    if (end of file)
    {
      remove file from list
    }
  } while (most recent number <= last number read from the second file)
       or (file list not empty)

  if (file list not empty)
  {
    sort files by last read number (you only need to reposition the first file)
  }
}

附言:删除了此解决方案的意外副本

P.S.: removed accidental copy of this solution

这篇关于排序问题-一遍算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！