本文主要是介绍[python算法]递归+查找+排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• 递归
• • 汉诺塔问题
• 查找
• • 顺序查找
  • 折半查找
• 排序(low b版)
• • 冒泡排序
  • 选择排序
  • 插入排序
  • low b版排序总结

递归

通俗的讲就是自调用

汉诺塔问题

汉诺塔问题:一次只能移动一个盘子
思路:
把n-1个盘子从A经过C移动到B
把第n个盘子从A移动到C
把n-1个盘子从B经过A移动到C

def hanoi(n, a, b, c):
    """
    :param n: 盘子数量
    :param a: a柱子
    :param b: b柱子
    :param c: c柱子
    :return:
    """
    if n > 0:
        hanoi(n - 1, a, c, b)            # 把n-1个盘子从A经过C移动到B
        print('移动 %s 到 %s ' % (a, c))  # 把第n个盘子从A移动到C
        hanoi(n - 1, b, a, c)            # 把n-1个盘子从B经过A移动到C

查找

在数列中查找值的下标，列表的index()是顺序查找

顺序查找

def linear_search1(val, li):
    """
    顺序查找
    时间复杂度:O(n)
    :param val:
    :param li:
    :return:
    """
    for i in range(len(li)):
        if li[i] == val:
            return i
    return None





    
def linear_search2(val, li):
    for ind, v in enumerate(li):
        if v == val:
            return ind
    return None

折半查找

折半查找的条件是数列要排好序

def binary_search(li, val):
    """
    折半查找
    时间复杂度:O(logn)
    :param li: 排序好的数列
    :param val: 要查找的值
    :return:下标
    """
    right = len(li) - 1
    left = 0
    while left <= right:  # 候选区有值
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            right = mid - 1
        elif li[mid] < val:
            left = mid + 1
    return None

排序(low b版)

冒泡排序

def bubble_sort(li):
    """
    冒泡排序
    时间复杂度:O(n**2)
    左右相互交换
    一趟排序完成后有序区增加一个数，无序区减少一个数
    :param li: 数列
    :return:
    """
    for i in range(len(li) - 1):  # 第i趟
        for j in range(len(li) - i - 1):  # 下标
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]

改进冒泡排序思路：如果某次循环未发生交换，则认为已经排序完成

def new_bubble_sort(li):
    """
    改进冒泡排序
    某一趟如果不发生换位，则退出
    :param li:
    :return:
    """
    for i in range(len(li) - 1):  # 第i趟
        exchange = False
        for j in range(len(li) - i - 1):  # 下标
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        if not exchange:
            return

选择排序

def select_sort(li):
    """
    选择排序
    从无序区拿出一个最小值放到有序区
    默认第一个数为有序区
    时间复杂度:O(n**2)
    :param li:
    :return:
    """
    for i in range(len(li) - 1):  		 # 最后一个数已经排好
        min_location = i  				 # i为无序区的最后一个值
        for j in range(i + 1, len(li)):  # 遍历无序区找最小值
            if li[j] < li[min_location]:
                min_location = j
        li[i], li[min_location] = li[min_location], li[i]

插入排序

def insert_sort(li):
    """
    插入排序
    默认列表最右边为有序区
    从无序区拿一个根据大小放到有序区
    时间复杂度:O(n**2)
    :param li:
    :return:
    """
    for i in range(1, len(li)):  # i为无序区的下标
        tmp = li[i]
        j = i - 1  # 有序区下标
        while j >= 0 and li[j] > tmp:
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tmp

low b版排序总结

均为原地操作，时间复杂度均为O(n**2)

这篇关于[python算法]递归+查找+排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！