20190516-归并排序

def mergeTwoLists(nums1,nums2):

    '''使用双指针，比较2个列表中的元素，如果相等则记录结果，如果不相等则挪动指针指向的值较小的列表指针，指向其下一位，直到其中一个指针指向列表的末尾'''

    nums1_index = 0

    nums2_index = 0

    result = []

    while nums1_index<len(nums1) and nums2_index<len(nums2):

        if nums1[nums1_index]==nums2[nums2_index]:

            result.append(nums1[nums1_index])

            nums1_index+=1

            nums2_index+=1

        elif nums1[nums1_index]>nums2[nums2_index]:

            nums2_index+=1

        else:

            nums1_index+=1

return result

print(mergeTwoLists([1,2,3],[1,2,4]))

print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))

def mergeTwoLists(nums1,nums2):

    result = []

    while nums1 and nums2:#当2个列表非空的时候进行对比

        if nums1[0] == nums2[0]:#当2个列表的第一个元素相等的时候记录result，然后同时将2个列表的第一个元素弹出，使列表第二个元素变成列表的第一个元素再次重复比较

            result.append(nums1[0])

            nums1 = nums1[1:]

            nums2 = nums2[1:]

        elif nums1[0]>nums2[0]: #如果列表1的第一个元素大于列表2的第一个元素，则切片修改第二个列表，使列表2的第2个元素变成第一个元素，继续对比

            nums2 = nums2[1:]

        else:

            nums1 = nums1[1:]

    return result

print(mergeTwoLists([1,2,3],[1,2,4]))

print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))

def mergeTwoLists(nums1,nums2):   

    '''遍历len(nums1)+len(nums2)次，当pop的时候报异常的时候结束遍历'''

    result = []

    for i in range((len(nums1)+len(nums2))):

        try:

            if nums1[0] == nums2[0]:#遍历的时候当两个列表的第1个元素相等的时候，将该元素插入结果列表，然后同时将2个列表的第一个元素弹出，让第二个元素变成第一个元素

                result.append(nums1.pop(0))

                nums2.pop(0)

            elif nums1[0]>nums2[0]:# 如果列表1的第一个元素大于列表2的第一个元素，则将列表2中的第一个元素弹出，使列表2的第2个元素变成第一个元素，继续对比

                nums2.pop(0)

            else:

                nums1.pop(0)

        except:#当pop报错的时候证明某一个列表已经为空，已对比完2个列表，此时返回结果

            return result

print(mergeTwoLists([1,2,3],[1,2,4])) #输出[1,2]

print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))#输出[1,4,9]

def mergeTwoLists(nums1,nums2):

    nums1_index = 0#列表1的指针

    nums2_index = 0#列表2的指针

    result = []

    while nums1_index<len(nums1) and nums2_index<len(nums2):#定义2个指针，遍历2个列表

        if nums1[nums1_index]==nums2[nums2_index]:#如果值相等，则将结果都插入result中，然后指针分别后移一位，比较列表的下一位

            result.append(nums1[nums1_index])

            result.append(nums2[nums2_index])

            nums1_index+=1

            nums2_index+=1

        elif nums1[nums1_index]>nums2[nums2_index]:#如果其中有一个值大，则将较小的值插入result中，然后移动较小值的指针

            result.append(nums2[nums2_index])

            nums2_index+=1

        else:

            result.append(nums1[nums1_index])

            nums1_index+=1

    if nums1_index<len(nums1):

        result+=nums1[nums1_index:]

    else:

        result+=nums2[nums2_index:]

    return result

print(mergeTwoLists([1,2,4,9],[1,3,4,7,9])) #输出[1, 1, 2, 3, 4, 4, 7, 9, 9]