我一直在寻找自然 mergesort实现(链接列表)已有一段时间,但是没有运气。
Merge Sort a Linked List
在这里,我们既有递归实现又有迭代实现,但是我不知道如何将其转换为自然的归并排序。
在最佳情况下,如何检查运行以获得 O(n)复杂性?它不必是C/C++,可以是任何语言,甚至可以是伪代码。
谢谢你。
最佳答案
Wikipedia上有一个伪代码实现:
# Original data is on the input tape; the other tapes are blank
function mergesort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
while any records remain on the input_tape
while any records remain on the input_tape
merge( input_tape, output_tape, scratch_tape_C)
merge( input_tape, output_tape, scratch_tape_D)
while any records remain on C or D
merge( scratch_tape_C, scratch_tape_D, output_tape)
merge( scratch_tape_C, scratch_tape_D, input_tape)
# take the next sorted chunk from the input tapes, and merge into the single given output_tape.
# tapes are scanned linearly.
# tape[next] gives the record currently under the read head of that tape.
# tape[current] gives the record previously under the read head of that tape.
# (Generally both tape[current] and tape[previous] are buffered in RAM ...)
function merge(left[], right[], output_tape[])
do
if left[current] ≤ right[current]
append left[current] to output_tape
read next record from left tape
else
append right[current] to output_tape
read next record from right tape
while left[current] < left[next] and right[current] < right[next]
if left[current] < left[next]
append current_left_record to output_tape
if right[current] < right[next]
append current_right_record to output_tape
return
关于sorting - 自然mergesort链表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10262602/