选择排序
def selection_sort(arr):
# 获取列表的长度
n = len(arr)
# 遍历整个列表
for i in range(n):
# 假设当前元素是最小的
min_idx = i
# 从 i+1 位置开始，遍历剩下的元素，寻找真正最小的那个
for j in range(i + 1, n):
# 如果找到了比当前假设的最小值还小的元素
if arr[j] < arr[min_idx]:
# 更新最小值的索引
min_idx = j
# 找到了最小值的索引后，将它和当前位置 i 的元素进行交换
# 也就是把最小的元素放到已排序部分的末尾
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 返回排序好的列表
return arr
# 示例
my_list = [64, 25, 12, 22, 11]
sorted_list = selection_sort(my_list)
print("原始列表:", [64, 25, 12, 22, 11])
print("排序后的列表:", sorted_list)排序算法
def insertion_sort(arr):
# 获取列表的长度
n = len(arr)
# 从第二个元素开始遍历，因为第一个元素默认是已排序的
for i in range(1, n):
# 待插入的元素
key = arr[i]
# 从已排序部分的最后一个元素开始，向左遍历
j = i - 1
# 在已排序部分中寻找 key 的正确插入位置
# 当 arr[j] > key 时，说明 arr[j] 需要向右移动
while j >= 0 and arr[j] > key:
# 将大于 key 的元素向右移动一位
arr[j + 1] = arr[j]
# 继续向左比较
j -= 1
# 找到正确位置后，将 key 插入
arr[j + 1] = key
# 返回排序好的列表
return arr
# 示例
my_list = [12, 11, 13, 5, 6]
sorted_list = insertion_sort(my_list)
print("原始列表:", [12, 11, 13, 5, 6])
print("排序后的列表:", sorted_list)快速排序
def quick_sort(arr):
# 调用内部的递归函数
_quick_sort(arr, 0, len(arr) - 1)
return arr
def _quick_sort(arr, low, high):
"""递归排序函数"""
if low < high:
# p_index 是分区操作后基准元素的索引
p_index = _partition(arr, low, high)
# 递归对基准左边的子列表排序
_quick_sort(arr, low, p_index - 1)
# 递归对基准右边的子列表排序
_quick_sort(arr, p_index + 1, high)
def _partition(arr, low, high):
"""分区函数，返回基准元素的索引"""
# 选择最后一个元素作为基准
pivot = arr[high]
i = low - 1 # i 用于记录小于基准的元素的边界
for j in range(low, high):
# 如果当前元素小于等于基准
if arr[j] <= pivot:
i += 1
# 交换 arr[i] 和 arr[j]，将小于基准的元素放到前面
arr[i], arr[j] = arr[j], arr[i]
# 最后将基准放到正确的位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 示例
my_list = [10, 7, 8, 9, 1, 5]
sorted_list = quick_sort(my_list)
print("快速排序前的列表:", [10, 7, 8, 9, 1, 5])
print("快速排序后的列表:", sorted_list)归并排序
def merge_sort(arr):
# 递归终止条件：如果列表只有一个或零个元素，它就是有序的
if len(arr) <= 1:
return arr
# 分解步骤：找到中间点，将列表一分为二
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 递归地对左右两个子列表进行排序
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
# 合并步骤：将两个已排序的子列表合并
return _merge(left_sorted, right_sorted)
def _merge(left, right):
"""合并函数，将两个有序列表合并成一个"""
merged_list = []
i = j = 0 # i 和 j 分别指向左右列表的第一个元素
# 比较左右列表的元素，并将其按顺序放入新列表
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged_list.append(left[i])
i += 1
else:
merged_list.append(right[j])
j += 1
# 将剩余的元素（如果存在）添加到新列表末尾
merged_list.extend(left[i:])
merged_list.extend(right[j:])
return merged_list
# 示例
my_list = [12, 11, 13, 5, 6, 7]
sorted_list = merge_sort(my_list)
print("归并排序前的列表:", [12, 11, 13, 5, 6, 7])
print("归并排序后的列表:", sorted_list)冒泡排序
def bubble_sort(arr):
n = len(arr)
# 外层循环控制遍历的轮次
for i in range(n):
# 内层循环进行相邻元素的比较和交换
# -1 是因为最后一个元素在比较时不需要再看它的下一个
# -i 是因为每轮结束后，末尾的 i 个元素已经是有序的了
for j in range(0, n - i - 1):
# 如果前面的元素大于后面的元素，就交换它们
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 示例
my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print("冒泡排序前的列表:", [64, 34, 25, 12, 22, 11, 90])
print("冒泡排序后的列表:", sorted_list)堆排序
def heap_sort(arr):
n = len(arr)
# 1. 建堆：从最后一个非叶子节点开始，自下而上地建堆
# n // 2 - 1 是最后一个非叶子节点的索引
for i in range(n // 2 - 1, -1, -1):
_heapify(arr, n, i)
# 2. 排序：将堆顶元素依次放到列表末尾
for i in range(n - 1, 0, -1):
# 将堆顶元素（最大值）与当前堆的最后一个元素交换
arr[i], arr[0] = arr[0], arr[i]
# 重新调整剩余部分为大顶堆
_heapify(arr, i, 0)
return arr
def _heapify(arr, n, i):
"""
堆化函数：将以 i 为根的子树调整为大顶堆
n 是堆的大小，i 是根节点的索引
"""
largest = i # 假设根节点是最大的
left = 2 * i + 1 # 左子节点的索引
right = 2 * i + 2 # 右子节点的索引
# 检查左子节点是否存在且大于根节点
if left < n and arr[left] > arr[largest]:
largest = left
# 检查右子节点是否存在且大于当前最大值
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大的不是根节点，就进行交换
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# 递归地调整被交换的子树
_heapify(arr, n, largest)
# 示例
my_list = [12, 11, 13, 5, 6, 7]
sorted_list = heap_sort(my_list)
print("堆排序前的列表:", [12, 11, 13, 5, 6, 7])
print("堆排序后的列表:", sorted_list)123