递归算法
#!/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)
#!/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)
"""
快排:
快速排序是对冒泡排序的一种改进。其基本思路是：
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)