我要评论插入排序
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
def insertion_sort(arr):
# 从数组的第二个元素开始遍历数组
for i in range(1, len(arr)):
key = arr[i] # 取出当前要插入的元素
j = i - 1 # 从当前元素的前一个元素开始向前比较
# 当前面的元素大于key，并且索引j不越界时，将前面的元素向后移动
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1 # 索引j向前移动
arr[j + 1] = key # 将key插入到正确的位置
希尔排序
希尔排序是插入排序的一种更高效的改进版本。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序使用一个序列h1, h2, …, ht（称为增量序列）来定义每个比较之间的"距离"。
def shell_sort(arr):
n = len(arr)
gap = n // 2 # 初始化间隔大小为n/2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
# 类似于插入排序，但是比较的间隔是gap
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2 # 间隔大小减半
选择排序
选择排序的工作原理是不断地选择剩余元素中的最小（或最大）元素，放到已排好序的序列的末尾，直到排序完整个序列。
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i # 假设当前索引的元素是最小的
for j in range(i+1, len(arr)):
# 如果找到比当前最小元素更小的元素，更新最小元素的索引
if arr[min_idx] > arr[j]:
min_idx = j
# 将找到的最小元素与当前位置的元素交换
arr[i], arr[min_idx] = arr[min_idx], arr[i]
冒泡排序
冒泡排序重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = false # 标记本轮是否发生了交换
for j in range(0, n-i-1):
# 如果前一个元素大于后一个元素，交换它们
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true # 发生了交换
# 如果一轮下来没有发生交换，说明数组已经有序，可以提前结束排序
if not swapped:
break
快速排序
快速排序使用分治法策略来把一个序列分为较小的序列。从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分区（partitioning）操作。
def quick_sort(arr):
if len(arr) <= 1:
return arr # 基本情况：数组长度为0或1时，直接返回数组
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 quick_sort(left) + middle + quick_sort(right)
发表评论