160 views
Python开发 / 数据结构与算法

7.递归、冒泡、快排算法

文章目录

递归算法

#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site: 
@software: PyCharm
@file: 7_recursion_Bubbling.py
@time: 2019/11/18 上午10:30
"""
#+++++++++++++++++++++++++++++++++++#
"""
递归:如果函数包含了对其自身的调用,则,该函数就是递归

递归应具备以下条件:
1.一个问题的解可以分解为几个子问题的解
2.这个问题与分解之后的子问题,除了数据规模不同,求解过程完全一样
3.存在递归终止条件
"""

def recursion(n):

    if n == 1:  # 递归终止条件是你=1
        return 1
    return recursion(n - 1) + n  # 调用自身


print('递归: ',recursion(10))


# f(4) = f(3) + 4 第一次进入
# f(3) = f(2) + 1 第二次进入
# f(2) = f(1) + 2
# f(1) = f(1) 触发判断条件,函数终止,返回1

# 斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
def f(n):
    if n <=0:
        return
    if n == 1:
        return 0
    if n == 2:
        return 1
    return f(n - 1) + f(n - 2)

print('斐波那契数列: ',f(35))
-----------------------结果----------------------------
递归:  55
斐波那契数列:  5702887

冒泡算法

"""
冒泡排序算法的运作如下:
1.比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
"""


def bubble_sort(alist):
    for j in range(len(alist) - 1, 0, -1):
        # j表示每次遍历需要比较的次数,是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]


li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(li)
print(li)
-----------------------结果----------------------------
[17, 20, 26, 31, 44, 54, 55, 77, 93]

快排

"""
快排:
快速排序是对冒泡排序的一种改进。其基本思路是:
1.通过一趟排序将待排序记录分割成独立的两部分,
2.其中一部分记录的关键字均比另一部分记录的关键字小,
3.则可分别对这两部分记录继续进行排序,以达到整个序列有序。
举例:
对“6 1 2 7 9 3 4 5 10 8”进行排序。
首先在这个序列中找一个数作为关键字(枢轴)。
1.为了方便,选取第一个数6作为关键字。
2.之后要将这个序列中所有比关键字6大的数放在它的右边,比关键字6小的数放在它的左边,
3.类似下面这种排列:3 1 2 5 4 6 9 7 10 8
4.一直重复
特点:
1、递归拆分
2、拆分到最后,所有小组内的元素个数都是1
一句话:递归拆分到不能再拆
"""


def quick_sort(li, start, end):
    # 分治 一分为二
    # start=end ,证明要处理的数据只有一个
    # start>end ,证明右边没有数据
    if start >= end:
        return
    # 定义两个游标,分别指向0和末尾位置
    left = start
    right = end
    # 把0位置的数据,认为是中间值
    mid = li[left]
    while left < right:
        # 让右边游标往左移动,目的是找到小于mid的值,放到left游标位置
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        # 让左边游标往右移动,目的是找到大于mid的值,放到right游标位置
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    # while结束后,把mid放到中间位置,left=right
    li[left] = mid
    # 递归处理左边的数据
    quick_sort(li, start, left - 1)
    # 递归处理右边的数据
    quick_sort(li, left + 1, end)


if __name__ == '__main__':
    l = [3,2,1,5,6,5,4]
    quick_sort(l, 0, len(l) - 1)
    print(l)
    # 稳定性:不稳定
    # 最优时间复杂度:O(nlogn)
    # 最坏时间复杂度:O(n^2)