小编点评

**递归思路** 递归是一种迭代算法，通过递归地调用自身方法来解决问题。递归思路的步骤如下： 1. **基 cases：**如果当前问题已经完全解决，则返回一个已知的解决方案。 2. **递归：**如果当前问题可以被分解成多个子问题，则递归解决这些子问题并合并他们的解决方案。 3. **合并：**如果当前问题可以被合并成一个新问题，则将其和其他子问题的解决方案合并起来。 **示例：** ```python def merge(li, low, mid, high): # 递归地解决左右两边的子问题 ltmp = [] while i <= mid and j <= high: if li[i] < li[j]: ltmp.append(li[i]) i += 1 else: ltmp.append(li[j]) j += 1 # 处理右边的剩余元素 while i <= mid: ltmp.append(li[i]) i += 1 # 处理左边的剩余元素 while j <= high: ltmp.append(li[j]) j += 1 # 将左右两边的元素合并起来 li[low:high + 1] = ltmp ``` **递归排序算法：** ```python def merge_sort(li, low, high): # 只有两个元素时，已排序 if low < high: mid = (low + high) // 2 merge_sort(li, low, mid) merge_sort(li, mid + 1, high) merge(li, low, mid, high) ``` **总结：** 递归是一种解决问题的算法，通过迭代地调用自身方法来解决问题。递归思路的步骤是基 cases、递归和合并。递归排序算法是一种基于递归的排序算法，它通过递归地将数组分割并排序。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

递归思路

• 

# _*_coding:utf-8_*_

import random


def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:  # 只要左右两边都有数
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    # while执行完，肯定有一部分没数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high + 1] = ltmp


def merge_sort(li, low, high):
    if low < high:  # 至少有两个元素，递归
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)


li = list(range(10))

random.shuffle(li)
print(li)
merge_sort(li, 0, len(li) - 1)
print(li)