乐趣区

关于python:玩转Python插入排序从基础到进阶

jiezi

插入排序是一种简略但无效的排序算法。它的根本思维是将待排序的元素一一插入已排序序列中的正确地位，直到所有元素都被插入实现。插入排序的算法复杂度为 O(n^2)，实用于小规模的数据排序。本文将介绍插入排序的原理、具体实现和优化，并提供相干的 Python 代码示例。

一、插入排序的基本原理

插入排序的基本原理能够用以下步骤形容：

  1. 将待排序序列的第一个元素看作已排序序列。
  2. 从第二个元素开始，一一将元素插入已排序序列的正确地位。
  3. 每次插入时，从后往前比拟已排序序列中的元素，将比以后元素大的元素顺次向后挪动，直到找到适合的插入地位。
  4. 反复步骤 3，直到所有元素都被插入实现，失去有序序列。

插入排序的关键在于找到插入地位并进行元素的后移操作。这种排序算法相似于咱们打扑克牌时整顿手中的牌，每次将一张新牌插入到已排序的牌中的正确地位。

二、插入排序的具体实现

上面是插入排序的具体实现代码：

def 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  # 将以后元素插入到正确地位

    return arr

三、插入排序的优化

插入排序是一种简略然而效率较低的排序算法，特地是对于大规模数据的排序。然而，咱们能够通过一些优化策略来进步插入排序的性能。

优化 1：缩小元素的比拟次数

在内层循环中，咱们能够通过应用“哨兵”来防止每次比拟都须要查看边界条件。咱们能够将待插入的元素复制到一个长期变量中，并将其作为哨兵，而后在内层循环中只比拟哨兵与已排序元素，而不是每次都拜访原始数组。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 以后待插入元素
        j = i - 1  # 已排序序列的最初一个元素的索引

        while arr[j] > key:
            arr[j + 1] = arr[j]  # 比以后元素大的元素向后挪动
            j -= 1

        arr[j + 1] = key  # 将以后元素插入到正确地位

    return arr

优化 2：应用二分查找确定插入地位

传统的插入排序是通过一一比拟已排序元素找到正确的插入地位。然而，咱们能够应用二分查找来确定插入地位，从而缩小比拟的次数。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 以后待插入元素
        left, right = 0, i - 1  # 已排序序列的左右边界

        while left <= right:
            mid = (left + right) // 2  # 两头地位
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1

        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]  # 比以后元素大的元素向后挪动

        arr[left] = key  # 将以后元素插入到正确地位

    return arr

四、总结

本文介绍了插入排序的原理、具体实现和优化。插入排序是一种简略但无效的排序算法，实用于小规模的数据排序。通过一直将元素插入已排序序列的正确地位，最终失去有序序列。咱们还介绍了两种优化策略，包含缩小元素的比拟次数和应用二分查找确定插入地位。这些优化能够进步插入排序的性能。通过把握插入排序的原理和优化办法，咱们能够更好地了解和利用这一罕用的排序算法。

五、最初

关注我，更多精彩内容立刻出现！

退出移动版