假设有2个有序列表l1、l2,如何效率比较高的将2个list合并并保持有序状态,这里默认排序是正序。
思路是比较简单的,无非是依次比较l1和l2头部第一个元素,将比较小的放在一个新的列表中,以此类推,直到所有的元素都被放到新的列表中。
考虑2个列表l1 = [2], l2 = [1],如何将他们合并呢?(注意:下面实现会改变l1和l2本来的值)
def signle_merge_sort(l1, l2): tmp = [] if l1[0] < l2[0]: tmp.append(l1[0]) tmp.extend(l2) del l2[0] else: tmp.append(l2[0]) tmp.extend(l1) del l1[0] return tmp
def recursion_merge_sort1(l1, l2): tmp = [] if len(l1) == 0: tmp.extend(l2) return tmp elif len(l2) == 0: tmp.extend(l1) return tmp else: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] tmp += recursion_merge_sort1(l1, l2) return tmp
def _recursion_merge_sort2(l1, l2, tmp): if len(l1) == 0 or len(l2) == 0: tmp.extend(l1) tmp.extend(l2) return tmp else: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] return _recursion_merge_sort2(l1, l2, tmp)def recursion_merge_sort2(l1, l2): return _recursion_merge_sort2(l1, l2, [])
def loop_merge_sort(l1, l2): tmp = [] while len(l1) > 0 and len(l2) > 0: if l1[0] < l2[0]: tmp.append(l1[0]) del l1[0] else: tmp.append(l2[0]) del l2[0] tmp.extend(l1) tmp.extend(l2) return tmp