思维导图
一、经典冒泡
冒泡排序：是一种简单的排序算法，它重复的遍历要排序的序列，一次比较两个元素，如果他们的顺序错误，就把他们交换过来。
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码如下：
def bubble_sort(lst):
n = len(lst)
# 遍历所有数组元素
for i in range(n):
# 由于每次遍历都会将最大的元素移动到末尾，
# 所以每次遍历都可以少比较一次已经排好序的末尾元素
for j in range(0, n - i - 1):
# 如果当前元素比下一个元素大，则交换它们
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
# 测试代码
lis = [34, 2, 67, 43, 99, 43, 9, 12, 71]
bubble_sort(lis)
print(lis)二、选择排序
选择排序的运作如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码示例：
def selection_sort(lst: list) -> list:
n = len(lst)
for i in range(n):
# 假设当前位置i是最小值的索引
min_index = i
# 在剩余未排序部分中找到最小值的索引
for j in range(i + 1, n):
if lst[j] < lst[min_index]:
min_index = j
# 将找到的最小值与当前位置i的值进行交换
lst[i], lst[min_index] = lst[min_index], lst[i]
# 测试代码
lis = [34, 2, 67, 43, 99, 43, 9, 12, 71]
sorted_lis = selection_sort(lis) # 调用函数并接收排序后的列表（尽管原列表已被修改）
print(sorted_lis) # 打印排序后的列表三、插入排序
概念和原理：
定义：每次将待排序中的第一个元素，放入已排序列表中对应的位置
原理：每一步从待排序列中选取第一个元素，将其插入到之前已排序序列中，直到待排序列所有元素排完，则结束排序
def insert_sort(l: list):
for i in range(1, len(l)):
key = l[i] # 保存当前要插入的元素
j = i
# 将大于key的已排序元素向后移动一个位置
while j > 0 and l[j-1] > key:
l[j] = l[j-1]
j -= 1
# 将key插入到正确的位置
l[j] = key
# 测试代码
lis = [34, 2, 67, 43, 99, 43, 9, 12, 71]
insert_sort(lis)
print(lis) # 输出应该是 [2, 9, 12, 34, 43, 43, 67, 71, 99]四、快速排序
基本思想：
- 快速排序是一种分治算法。
- 它选择一个基准元素（pivot），将数组分成两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
- 然后递归地对这两部分进行快速排序
代码如下：
def part(l:list,left,right):
p=l[left]
while left<right:
while l[right]>=p and left<right:
right-=1
l[left]=l[right]
while l[left]<=p and left<right:
left+=1
l[right]=l[left]
l[left]=p
return left
def quick_sort(l:list,left,right):
if left<right:
p_index=part(l,left,right)
quick_sort(l,left,p_index-1)
quick_sort(l,p_index+1,right)
lis=[34,2,67,43,99,43,9,12,71]
quick_sort(lis,0,len(lis)-1)
print(lis)
或者用列表推导式：
def quicksort(arr):
"""
对输入的数组进行快速排序。
参数:
arr (list): 需要排序的数组
返回:
list: 排序后的数组
"""
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2] # 选择中间元素作为基准
left = [x for x in arr if x < pivot] # 所有小于基准的元素
middle = [x for x in arr if x == pivot] # 所有等于基准的元素
right = [x for x in arr if x > pivot] # 所有大于基准的元素
return quicksort(left) + middle + quicksort(right)
# 测试代码
if __name__ == "__main__":
sample_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quicksort(sample_array)
print("排序后的数组:", sorted_array)五、希尔排序
称为递减增量排序。它通过比较距离较远的元素来工作，然后逐渐减少这个间隔，直到它变成1，这时数组就几乎是有序的了，最后进行一次普通的插入排序。
def quicksort(arr):
"""
对输入的数组进行快速排序。
参数:
arr (list): 需要排序的数组
返回:
list: 排序后的数组
"""
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2] # 选择中间元素作为基准
left = [x for x in arr if x < pivot] # 所有小于基准的元素
middle = [x for x in arr if x == pivot] # 所有等于基准的元素
right = [x for x in arr if x > pivot] # 所有大于基准的元素
return quicksort(left) + middle + quicksort(right)
# 测试代码
if __name__ == "__main__":
sample_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quicksort(sample_array)
print("排序后的数组:", sorted_array)