4 篇笔记 写笔记

1. #0

   吴sp

   163***[email protected]

   49

   参考方法:

   #定义归并排序函数
   def merge_sort(lst):
    if len(lst) <= 1:
    return lst
    middle = int (len(lst)/2)
    left = merge_sort(lst[ :middle])#左边
    right = merge_sort(lst[middle: ])#右边
    merged = []
    while left and right:
    merged.append(left.pop(0) if left [0] <= right[0] else right.pop(0))
    merged.extend(right if right else left) #该方法没有返回值,但会在已存在的列表中添加新的列表内容
    return merged
   data_lst = [6,202,100,301,38,8,1]
   print(merge_sort(data_lst))

   吴sp

   163***[email protected]

   7年前 (2019年08月01日)
2. #0

   Leonard.Tang

   343***[email protected]

   7

   归并就是分儿治之:

   def MergeSort(left, right):
    # 比较传过来的两个序列left,right,返回一个排好的序列
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
    if left[i] <= right[j]:
    result.append(left[i])
    i += 1
    else:
    result.append(right[j])
    j += 1
    result += left[i:] # 这时候i或者j到了序列的最后
    result += right[j:]
    print(result)
    return result
   def SortByMerge(arr, size):
    if size <= 1:
    return arr
    i = int(size/2)
    left = SortByMerge(arr[:i], i)
    right = SortByMerge(arr[i:], size - i)
    return MergeSort(left, right)
   arr = [12, 11, 13, 5, 7, 6]
   print(SortByMerge(arr, len(arr)))

   Leonard.Tang

   343***[email protected]

   7年前 (2019年08月08日)
3. #0

   老实人

   www***[email protected]

   15

   参考方法:

   def merge_sort( li ):
    #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素,不再拆分了
    if len(li) == 1:
    return li
    #取拆分的中间位置
    mid = len(li) // 2
    
    #拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]
    #对拆分过后的左右再拆分 一直到只有一个元素为止
    #最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort( left )
    rl =merge_sort( right )
    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll , rl)
    
   #这里接收两个列表
   def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较,把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
    #为了保持稳定性,当遇到相等的时候优先把左侧的数放进结果列表,因为left本来也是大数列中比较靠左的
    if left[0] <= right[0]:
    result.append( left.pop(0) )
    else:
    result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了,我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result
   if __name__ == '__main__':
    li = [5,4 ,3 ,2 ,1]
    li2 = merge_sort(li)
    print(li2)

   老实人

   www***[email protected]

   7年前 (2019年09月03日)
4. #0

   Gbosh

   ge1***[email protected]

   0

   参考方法:

   def merge(s1,s2,s):
    """将两个列表是s1,s2按顺序融合为一个列表s,s为原列表"""
    # j和i就相当于两个指向的位置,i指s1,j指s2
    i = j = 0
    while i+j<len(s):
    # j==len(s2)时说明s2走完了,或者s1没走完并且s1中该位置是最小的
    if j==len(s2) or (i<len(s1) and s1[i]<s2[j]):
    s[i+j] = s1[i]
    i += 1
    else:
    s[i+j] = s2[j]
    j += 1
   def merge_sort(s):
    """归并排序"""
    n = len(s)
    # 剩一个或没有直接返回,不用排序
    if n < 2:
    return
    # 拆分
    mid = n // 2
    s1 = s[0:mid]
    s2 = s[mid:n]
    # 子序列递归调用排序
    merge_sort(s1)
    merge_sort(s2)
    # 合并
    merge(s1,s2,s)
   if __name__ == '__main__':
    s = [1,7,3,5,4]
    merge_sort(s)
    print(s)

   Gbosh

   ge1***[email protected]

   4年前 (2022年09月14日)