Python 中的插入排序和计数比较/交换
插入排序是一种简单的排序算法,它逐步构建最终排序的序列。在每一次迭代中,它将当前元素插入到已排序序列的正确位置。下面是 Python 中实现插入排序的代码:
pythonCopy codedef insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # 示例用法 my_list = [5, 2, 8, 12, 1] insertion_sort(my_list) print(my_list) # 输出: [1, 2, 5, 8, 12]
上述代码中,insertion_sort 函数接受一个列表作为输入,并对其进行原地排序。
insertion_sort
在插入排序的每一次迭代中,从索引 1 开始,我们将当前元素 key 存储在变量中,然后将其与已排序的子列表中的元素进行比较。如果已排序的元素大于 key,则将该元素向右移动一个位置,为 key 腾出空间。重复这个过程直到找到合适的位置,然后将 key 插入到正确的位置。
key
计数比较和交换是一种用于计算排序算法中的技术。它用于追踪排序过程中进行的比较和交换操作的数量。这可以用来衡量算法的效率。下面是一个简单的示例,演示如何在插入排序中实现计数比较和交换:
pythonCopy codedef insertion_sort(arr): comparisons = 0 swaps = 0 for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: comparisons += 1 arr[j + 1] = arr[j] swaps += 1 j -= 1 comparisons += 1 arr[j + 1] = key return comparisons, swaps # 示例用法 my_list = [5, 2, 8, 12, 1] comp, swaps = insertion_sort(my_list) print(my_list) # 输出: [1, 2, 5, 8, 12] print(comp, swaps) # 输出: 7 4
在上述示例中,我们添加了两个变量 comparisons 和 swaps 来追踪比较和交换的数量。在每次比较和交换操作时,我们将相应的计数器增加1。在排序完成后,我们可以使用这些计数器来获得比较和交换的总数。
comparisons
swaps
请注意,这只是一个简单示例,用于演示计数比较和交换的概念。在实际应用中,你可能需要根据算法的实现方式和需求