在Ruby中实现链表的合并排序可以通过以下步骤完成:
class ListNode
attr_accessor :value, :next
def initialize(value)
@value = value
@next = nil
end
end
def create_linked_list(arr)
head = ListNode.new(arr[0])
current = head
(1...arr.length).each do |i|
node = ListNode.new(arr[i])
current.next = node
current = node
end
head
end
def merge_sort(head)
return head if head.nil? || head.next.nil?
mid = find_middle(head)
left = head
right = mid.next
mid.next = nil
merge(merge_sort(left), merge_sort(right))
end
def find_middle(head)
slow = head
fast = head
while fast.next && fast.next.next
slow = slow.next
fast = fast.next.next
end
slow
end
def merge(left, right)
dummy = ListNode.new(0)
current = dummy
while left && right
if left.value < right.value
current.next = left
left = left.next
else
current.next = right
right = right.next
end
current = current.next
end
current.next = left if left
current.next = right if right
dummy.next
end
def test_merge_sort(arr)
head = create_linked_list(arr)
sorted_head = merge_sort(head)
print_linked_list(sorted_head)
end
def print_linked_list(head)
current = head
while current
print "#{current.value} "
current = current.next
end
puts
end
test_merge_sort([4, 2, 1, 3]) # 输出:1 2 3 4
通过以上步骤,我们可以在Ruby中实现链表的合并排序算法。这个算法的时间复杂度为O(nlogn),其中n是链表的长度。在实际应用中,链表的合并排序可以用于对大量数据进行排序,例如日志文件的排序、搜索引擎的排名等。
腾讯云相关产品和产品介绍链接地址:
领取专属 10元无门槛券
手把手带您无忧上云