用合并错误输出对订单排序

Question

我必须设计一个算法来按选择时间(t选择，在仓库中找到好的东西并将其带到表面)加上发货时间(t运送，常数)来排序订单列表。客户订单可以从服务器数据库中检索(顺序与所放置的顺序相同)。您应该期望在100到10K之间的元素。

该程序以一组订单作为输入，其中id、t选择和t传送类型为无符号int，n是订单数和空格字符。

id1, t selection1, t shipping1; ...; idn, t selectionn, t shippingn \n

预期输出是is的空格分隔列表，按t选择+t传送排序，并以新行\n结束。

Input: 1, 500, 100; 2, 700, 100; 3, 100, 100\n

Output: 3 1 2\n

我试图用合并排序来完成它，但是我的程序会返回。

1 2 3/n instead of 3 1 2/n

我已经提供了下面的代码，有人能帮我吗？

#!/usr/bin/env python3
import sys


class Order:
    def __init__(self, id: int, selection_time: int, shipping_time: int):
        self.id: int = id
        self.selection_time: int = selection_time
        self.shipping_time: int = shipping_time


def merge(left, right):
    if not len(left) or not len(right):
        return left or right
    result = []
    i, j = 0, 0
    while len(result) < len(left) + len(right):
        if left[i].shipping_time + left[i].selection_time < right[j].shipping_time + right[j].selection_time:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
    return result


def sort(list):
    if len(list) < 2:
        return list
    middle = int(len(list) / 2)
    left = sort(list[:middle])
    right = sort(list[middle:])
    return merge(left, right)


if __name__ == '__main__':
    '''
    Retrieves and splits the input
    '''
    data = input()
    data = data.split('; ')
    order_list = []
    for d in data:
        id, selection_t, shipping_t = d.split(', ', 2)
        order: Order = Order(int(id), int(selection_t), int(shipping_t))
        order_list.append(order)
    sort(order_list)
    for order in order_list:
        sys.stdout.write(str(order.id))
        sys.stdout.write(" ")

Answer 1

最简单(也可能是效率最低)的排序算法是气泡排序。但是这个问题并没有提到性能，所以它可以简化成这样：

class Order:
    def __init__(self, ident, selection_time, shipping_time):
        self._ident = ident
        self._selection_time = selection_time
        self._shipping_time = shipping_time
    @property
    def selection_time(self):
        return self._selection_time
    @property
    def shipping_time(self):
        return self._shipping_time
    @property
    def ident(self):
        return self._ident


def merge(lst):
    def comboval(order):
        return order.selection_time + order.shipping_time

    if len(lst) > 1:
        mid = len(lst) // 2
        left = lst[:mid]
        right = lst[mid:]
        merge(left)
        merge(right)
  
        i = j = k = 0
  
        while i < len(left) and j < len(right):
            if comboval(left[i]) < comboval(right[j]):
                lst[k] = left[i]
                i += 1
            else:
                lst[k] = right[j]
                j += 1
            k += 1

        for _i in range(i, len(left)):
            lst[k] = left[_i]
            k += 1

        for _j in range(j, len(right)):
            lst[k] = right[_j]
            k += 1

    return lst

inval = '1, 500, 100; 2, 700, 100; 3, 100, 100'

orderlist = []

for order in inval.split(';'):
    orderlist.append(Order(*map(int, order.split(','))))

print(*[order.ident for order in merge(orderlist)])

输出：

3 1 2

注：

这是一种就地排序