数据结构和算法-排序算法-插入排序
2023-09-14 08:59:04 时间
################## 插入排序 ####################
""" 插入算法: alist = [54,26,93,17,77,31,44,55,20] 还是把序列分为两部分, 一开始就把第一个数字认为是有序的, alist = [54, 26,93,17,77,31,44,55,20] 第一轮, 把第二部分的和第一部分的最后一个做比较,如果小就交换, alist = [26,54 93,17,77,31,44,55,20] 第二轮,把第二部分的第一个和第一部分的最后一个作比较,小就交换,然后再往前比较,如果小还需要交换, 所以总的实现就是把后面的第一个,一直和前面的从后往前比较,知道结束, 选择排序和插入排序比较: 插入排序是从第二部分取出第一个,然后和第一部分从头到尾去比较,然后插入进去, 和选择排序不一样,选择排序也是分为两部分,但是是比较后面的,比较出来最小的然后插入到第一部分的最后面去,这是选择排序, """
################## 插入排序 ####################
# 第一版: def insert_sort(alist): n=len(alist) for j in range(1,n): i = j while i>0: if alist[i] < alist[i-1]: alist[i],alist[i-1]= alist[i-1],alist[i] i -=1 else: break # 不加这一句也可以,但是可以优化最优的时间复杂度,对于有序的队列,内层的复杂度就变成1了, # 第二版: def insert_sort2(alist): # 从第二个位置,即下标为1的元素开始向前插入 for i in range(1, len(alist)): # 从第i个元素开始向前比较,如果小于前一个元素,交换位置 for j in range(i, 0, -1): if alist[j] < alist[j-1]: alist[j], alist[j-1] = alist[j-1], alist[j] # 外层循环是确保把第二部分的所有元素都取出来 # 内层循环是确保把取出来的值从后往前比较一遍,如果小就交换, if __name__ == '__main__': alist = [54,26,93,17,77,31,44,55,20] print(alist) insert_sort(alist) print(alist)
相关文章
- 【经典算法】直接选择排序
- Javascript算法系列之快速排序(Quicksort)
- Java实现 蓝桥杯 算法提高 成绩排序
- 浅入浅出 Java 排序算法
- java算法 -- 归并排序
- 数据结构和算法-排序算法-希尔排序
- 数据结构和算法-排序算法-冒泡排序
- (算法:二分查找)在排序数组中,找出给定数字出现的次数
- 【python cookbook】【数据结构与算法】13.通过公共键对字典列表排序
- 数据结构与算法之美-5 排序算法2 [MD]
- Python排序算法之选择排序定义与用法示例
- 算法入门---选择排序
- 数据结构和算法-排序算法-快速排序
- 数据结构和算法学习七,之快速排序
- 重新整理数据结构与算法(c#)—— 二叉树排序树补删除节点[二十二]
- Algorithm:C++语言实现之队列相关算法(最短路径条数问题、拓扑排序)
- 使用基于非支配排序的鲸鱼优化算法的生产过程中关键质量特征识别的多目标特征选择(Matlab代码实现)
- 10 大经典排序算法 Python 版实现(附动图演示)
- 【算法图文动画详解系列】QuickSort 快速排序算法
- 《数据结构与算法之美》——冒泡排序、插入排序、选择排序
- 排序算法
- Elias-Fano编码算法——倒排索引压缩用,本质上就是桶排序数据结构思路
- 面试官:手撕十大排序算法,你会几种?(转)
- 数据结构与算法之桶排序
- 数据结构与算法之选择排序(含改进版)
- 数据结构和算法 十七、排序算法
- DSA之十大排序算法第九种:Bucket Sort