python实现插入排序算法

简介: 插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...

插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。

python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实现如下:

def insert_sort(items):
    for i in range(1, len(items)):
        # 从第i个元素开始向前比较,如果小于前一个元素,交换位置
        for j in range(i, 0-1):
            if items[j] < items[j-1]:
                items[j], items[j-1] = items[j-1], items[j]

2019-04-16-23_38_24.png

插入排序的可应用于这样的场景:需要合并两个有序序列,并且合并后的序列依旧有序,此时插入排序可以排上用场。

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。

最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用

但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

相关文章
|
2天前
|
机器学习/深度学习 人工智能 算法
海洋生物识别系统+图像识别+Python+人工智能课设+深度学习+卷积神经网络算法+TensorFlow
海洋生物识别系统。以Python作为主要编程语言,通过TensorFlow搭建ResNet50卷积神经网络算法,通过对22种常见的海洋生物('蛤蜊', '珊瑚', '螃蟹', '海豚', '鳗鱼', '水母', '龙虾', '海蛞蝓', '章鱼', '水獭', '企鹅', '河豚', '魔鬼鱼', '海胆', '海马', '海豹', '鲨鱼', '虾', '鱿鱼', '海星', '海龟', '鲸鱼')数据集进行训练,得到一个识别精度较高的模型文件,然后使用Django开发一个Web网页平台操作界面,实现用户上传一张海洋生物图片识别其名称。
34 7
海洋生物识别系统+图像识别+Python+人工智能课设+深度学习+卷积神经网络算法+TensorFlow
|
2天前
|
机器学习/深度学习 人工智能 算法
【昆虫识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50
昆虫识别系统,使用Python作为主要开发语言。通过TensorFlow搭建ResNet50卷积神经网络算法(CNN)模型。通过对10种常见的昆虫图片数据集('蜜蜂', '甲虫', '蝴蝶', '蝉', '蜻蜓', '蚱蜢', '蛾', '蝎子', '蜗牛', '蜘蛛')进行训练,得到一个识别精度较高的H5格式模型文件,然后使用Django搭建Web网页端可视化操作界面,实现用户上传一张昆虫图片识别其名称。
42 7
【昆虫识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50
|
3天前
|
机器学习/深度学习 人工智能 算法
【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
球类识别系统,本系统使用Python作为主要编程语言,基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集 '美式足球', '棒球', '篮球', '台球', '保龄球', '板球', '足球', '高尔夫球', '曲棍球', '冰球', '橄榄球', '羽毛球', '乒乓球', '网球', '排球'等15种常见的球类图像作为数据集,然后进行训练,最终得到一个识别精度较高的模型文件。再使用Django开发Web网页端可视化界面平台,实现用户上传一张球类图片识别其名称。
31 7
【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
|
4天前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
5天前
|
存储 算法 Python
python常用算法(5)——树,二叉树与AVL树(一)
python常用算法(5)——树,二叉树与AVL树
|
1天前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
4 0
|
1天前
|
存储 机器学习/深度学习 算法
Python算法基础教程
Python算法基础教程
|
5天前
|
搜索推荐 算法
排序算法之插入排序
排序算法之插入排序
14 0
|
5天前
|
存储 算法 Shell
python常用算法(5)——树,二叉树与AVL树(三)
python常用算法(5)——树,二叉树与AVL树
|
5天前
|
算法 Python
python常用算法(5)——树,二叉树与AVL树(二)
python常用算法(5)——树,二叉树与AVL树