一、思维导图
二、冒泡排序
def bubble_sort(ls):
"""
用i循环,逐步比较相邻元素,直到循环结束,停止交换，就像一个个气泡从下往上冒泡,每一次的循环结果都是最大的元素到了后面已排序序列的列首。
"""
j = 0 # 用于确定循环次数,同时用于下面排除已排序序列
while j < len(ls):
i = 0 # 用于遍历未排序序列
while i < len(ls) - 1 - j: # -j排除已排序序列
# 两两比较
if ls[i] > ls[i + 1]:
ls[i], ls[i + 1] = ls[i + 1], ls[i]
i += 1
j += 1
三、选择排序
def selection_sort(ls):
"""
选择排序
逐步找到每个最小元素依次放入前面已排序列列尾
"""
i = 0 # 用于确定遍历次数，也可理解为已排好序的元素后的第一个位置
while i < len(ls) - 1:
m = i # 用于存放下标最小值,每次循环前需要重置为i,一次循环结束后交换m和j的位置
j = i + 1 # 用于 遍历i后面的所有元素与i对比，同时把遍历到的最小值赋值给m，
# 遍历j用于寻找最小的元素并用m标记
while j < len(ls):
if ls[j] < ls[m]:
m = j
j += 1
if m != i: # 避免无意义的交换
ls[i], ls[m] = ls[m], ls[i] # 将寻找到的最小元素交换到最前面
i += 1
四、直接插入排序
def insertion_sort(ls):
"""
直接插入排序
"""
i = 1 # 记录待排序列中的第一个元素,从1开始是因为第一步只插入了一个元素没必要排序
while i < len(ls):
temp = ls[i] # 用于保存当前元素的值
j = i # j用于向前遍历,逐步与temp比较,若j-1大于temp直接右移j-1,最后当j-1<=temp,空出来的位置填入temp
# j<0表示只有一个元素时不必排序
while temp < ls[j - 1] and j > 0:
ls[j] = ls[j - 1]
j -= 1
ls[j] = temp
i += 1
五、快速排序
def quick_sort_part(ls, L, R):
"""
快速排序
"""
# 定义基准
P = ls[L]
while R > L:
while ls[R] >= P and R > L: # R和L是会变化的,所以内循环也要检查 R 是否 > L
R -= 1
ls[L] = ls[R] # 比基准小的数据放在左边
while ls[L] <= P and R > L:
L += 1
ls[R] = ls[L] # 比基准大的数据放在右边
# 当L=R说明只剩最后一个元素，把P填进去
ls[L] = P # or ls[R] = P
return R # 返回当前基准,也可以return L
def quick_sort(ls, L, R):
"""
快速排序
"""
if R > L: # 只有当不止一个元素时才进行快排
# 进行第一次快排
P_index = quick_sort_part(ls, L, R)
# 递归,直到R>L
# 对基准左边的进行快排
quick_sort(ls, L, P_index - 1) # 此处递归结束表示第一次快排之后的左边部分已经排序完毕。
# 对基准右边的进行快排
quick_sort(ls, P_index + 1, R) # 此处递归结束表示第一次快排之后的右边部分已经排序完毕。
六、希尔排序
def shell_sort(ls):
"""
"""
n = len(ls) # ls的长度
gap = n // 2 # 初始化gap
# 确定外层循环次数
while gap > 0:
for i in range(gap, n): # 从与第一个元素相隔gap的元素开始遍历
j = i # 不能改变外循环的i，需要创建一个j用于比较
while j >= gap and ls[j] < ls[j - gap]: # j>=gap 判断 j-gap 是否会越界。ls[j]<ls[j-gap] 判断是否需要交换
ls[j - gap], ls[j] = ls[j], ls[j - gap] # 交换
j -= gap # 让当前元素继续向前跳跃 gap 步，去和更前面的同组元素比较，直到它到达正确的插入位置。
# 更新步长
gap = gap // 2
七、归并排序
# 定义归并排序算法
def merge_sort(alist):
"""
归并排序
"""
# 如果列表的元素个数小于等于1 直接返回
if len(alist) <= 1:
return alist
# 将列表从中间分割成两半
mid = len(alist) // 2
left_half = alist[:mid]
right_half = alist[mid:]
# 分别 递归 将左右两部分再次进行分割两半
"""
递归流程： 直到满足if len(alist) <= 1:之前会一直递归,无法执行到merge函数,满足if len(alist) <= 1:,之后left_half和right_half会被赋值,两个都是只有一个元素的列表
此时才能执行到合并函数merge,执行完之后会向递归的上一层的left_half或right_half返回合并后的列表，此时的left_half和right_half的某一个或者全部会变成两个元素的列表
然后回再次执行合并函数merge,直到整个递归流程结束，left_half和right_half为最初分开的两半,最后执行合并函数即完成整体合并
"""
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# 合并左右两部分的序列
return merge(left_half,right_half) # 合并
# 定义合并的算法
def merge(left,right):
"""
用于merge_sort递归合并的简单的合并并排序算法
"""
# 将排序好的额元素放入空列表中
arr = []
i=0 # 遍历左边列表中的每个元素
j=0 # 遍历右边列表中的每个元素
#比较两个列表中的元素 将小的元素先放入arr空列表中
while i<len(left) and j<len(right):
if left[i] < right[j]:
arr.append(left[i])
i+=1
else:
arr.append(right[j])
j+=1
# 如果右边列表由剩余元素 将它直接插入列表中
while j<len(right):
arr.append(right[j])
j+=1
# 如果左边列表由剩余元素 将它直接插入列表中
while i < len(left):
arr.append(left[i])
i += 1
return arr
八、二分查找
def binary_search_iter(arr, target):
"""
在 有序 升序 数组 arr 中查找 target。
返回其索引；若不存在返回 -1。
"""
left, right = 0, len(arr) - 1 # 闭区间 [left, right]
while left <= right: # 区间非空
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # 去右半边
else:
right = mid - 1 # 去左半边
return -1
ls = [1, 2, 5, 7, 9, 11, 13, 17, 19, 20]
print(binary_search_iter(ls, 9))