常用的算法思想包括：枚举、递归、分治、贪心、试探、动态迭代和模拟等
- 冒泡排序
# 算法复杂度：最坏：(n**2) 最好：O(n) 稳定
def bubble_sort(alist):
n = len(alist)
for i in range(n):
for j in range(0,n-i-1):
if alist[j]>alist[j+1]:
alist[j],alist[j+1]=alist[j+1],alist[j]
return alist
arr = [64, 34, 25, 12, 22, 11, 90]
new_arr = bubble_sort(arr)
print(new_arr)
- 快速排序
# 快速排序
def quickly_sort(alist,start,end):
# 递归的出口
if start>=end:
return
low = start
high = end
key = alist[start]
while low<high:
# 1.从右侧开始找比基准元素小的，放到左侧
while low<high and alist[high]>key:
high = high - 1
alist[low]=alist[high]
# 2.从左侧开始找比基准元素大的，放到右侧
while low<high and alist[low]<=key:
low = low + 1
alist[high]=alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
alist[low]=key
# 对基准元素左边的子序列进行快速排序
quickly_sort(alist,start,low-1)
# 对基准元素右边的子序列进行快速排序
quickly_sort(alist,low+1,end)
return alist
if __name__ == '__main__':
a = [49,38,65,97,76,13,27,49,10]
print(a)
new_a = quickly_sort(a,0,len(a)-1)
print(new_a)
- 链表
# 结点类
class Node(object):
# 初始化链表
def __init__(self,value):
self.value = value
self.next = None
# 获取结点数据
def get_data(self):
return self.value
# 更新结点数据
def set_data(self, new_value):
self.value = new_value
# 获取指针
def get_next(self):
return self.next
# 更新指针
def set_next(self,new_next):
self.next = new_next
# 链表的主要功能包括：节点的增加、删除和查询，返回链表的长度，返回链表是否为空等。
# 链表类 单链表
class ListNode(object):
def __init__(self,node=None):
self.__head = node
# 获取头指针
def get_head(self):
return self.__head
# 获取链表的长度
def length(self):
cur = self.__head
count = 0
while cur is not None:
cur = cur.next
count += 1
return count
def traverse(self,link_encode):
cur = link_encode
while cur is not None:
print(cur.value, end=' ')
cur = cur.next
print('')
# 节点的增加 从头部增加
def head_add(self,value):
new_node = Node(value)
new_node.next=self.__head
self.__head=new_node
# 节点的增加 从尾部增加
def tail_add(self,value):
new_node = Node(value)
cur = self.__head
if cur is None:
self.head_add(value)
else:
while cur.next is not None:
cur=cur.next
cur.next=new_node
new_node.next=None
# 节点的增加 从中间增加
def middle_add(self,value,pos):
new_node = Node(value)
if pos<=0:
self.head_add(value)
else:
cur = self.__head
for i in range(pos-1):
cur=cur.next
new_node.next = cur.next
cur.next = new_node
# 遍历输出链表
def travel(self):
cur = self.__head
while cur is not None:
print(cur.value,end=' ')
cur = cur.next
print('')
- 二分法
也称为折半法，是一种在有序数组中查找特定元素的搜索算法
# 二分法查找的思路如下：
# （1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
# （2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
# （3）如果某一步数组为空，则表示找不到目标元素。
# 二分法查找的时间复杂度O(logn)。
import math
def dichotomy(alist,key):
low = 0
high = len(alist)-1
if high<0:
print("数组为空")
return
while low<=high:
mid=(math.floor((low+high)/2))
if key==alist[mid]:
return mid+1,alist[mid]
elif key<alist[mid]:
high=mid-1
elif key>alist[mid]:
low=mid+1
else:
print("数组中没有该元素")
return
a = [1,2,3,4,5,6,7,8,9]
res,tmp = dichotomy(a,0)
print("数组中第",res,"个元素是要查找的值,值为",tmp)
- 二叉树遍历
- 字符串统计
str_a = "aabbbcccccccccccddddddddddddddddddddddddddd"
l = list(str_a)
print("出现的次数是：",l.count('d'))
- 字符串反转
# 方法一 函数
def reverse_s(s):
return s[::-1]
str_a = 'Hello'
print(reverse_s(str_a))
# 方法二 先转列表再reverse再转回字符串
l = list(str_a)
l.reverse()
# 列表转字符串
print(''.join(l))
- 实现斐波那契数列（递归的典型应用）
# 递归
# 1) 递归是在函数本身调用函数本身。
# 2) 递归的效率比较低，如果有时间限制不建议使用。
# 3) 递归过程中需要有一个明确的结束条件，即递归出口。
# 斐波那契数列的递推公式为F(n)=F(n-1)+F(n-2)，
# F(1)、和F(2)为1，我们可以通过递归来求解斐波那契数列中的某一项的值为多少。
def fibonacci(n):
if n<=0:
return
f = [1,1]
for i in range(2,n):
f.append(f[i-1] + f[i-2])
return f[n-1]
print(fibonacci(7))
- 汉诺塔问题（递归）
i = 1
def move(n,fr,to):
global i
print('这是第%d步:把%d号盘子从%s移动到%s'%(i,n,fr,to))
i += 1
def hanoi(n,a,b,c):
if n == 1:
move(1,a,c)
else:
hanoi(n-1,a,c,b)
move(n,a,c)
hanoi(n-1,b,a,c)
if __name__ == '__main__':
n = int(input('输入A上面盘子的数量:'))
print('移动开始')
hanoi(n,'A','B','C')
- 水仙花数
# 所谓"水仙花数"是指一个三位数，其各位数字立方和等于该本身。
# 例如：153是一个水仙花数，因为153=1^3+5^3+3^3。
count=0
for i in range(100,1000):
a = int(i/100) # 取第一位
b = int(i/10%10) # 取第二位
c = int(i%10) # 取最后一位
if i == (a**3 + b**3 + c**3):
count = count + 1
print("第", count, "个水仙数：" ,i)
网友评论