文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

玩转Python插入排序:从基础到进阶,成为排序专家

2024-11-30 07:57

关注

一、插入排序的基本原理

插入排序的基本原理可以用以下步骤描述:

  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

四、总结

本文介绍了插入排序的原理、具体实现和优化。插入排序是一种简单但有效的排序算法,适用于小规模的数据排序。通过不断将元素插入已排序序列的正确位置,最终得到有序序列。我们还介绍了两种优化策略,包括减少元素的比较次数和使用二分查找确定插入位置。这些优化可以提高插入排序的性能。通过掌握插入排序的原理和优化方法,我们可以更好地理解和应用这一常用的排序算法。

来源:子午Python内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯