admin

Python 中的插入排序和计数比较/交换

python

Python 中的插入排序和计数比较/交换


阅读 75

收藏
2023-05-20

共1个答案

admin

插入排序是一种简单的排序算法,它逐步构建最终排序的序列。在每一次迭代中,它将当前元素插入到已排序序列的正确位置。下面是 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 函数接受一个列表作为输入,并对其进行原地排序。

在插入排序的每一次迭代中,从索引 1 开始,我们将当前元素 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

在上述示例中,我们添加了两个变量 comparisonsswaps 来追踪比较和交换的数量。在每次比较和交换操作时,我们将相应的计数器增加1。在排序完成后,我们可以使用这些计数器来获得比较和交换的总数。

请注意,这只是一个简单示例,用于演示计数比较和交换的概念。在实际应用中,你可能需要根据算法的实现方式和需求

2023-05-20