支付网站建设费账务处理,沈阳网站设计公司,网站制作昆山,免费签名设计在线生成插入排序
插入排序#xff08;英语#xff1a;Insertion Sort#xff09;是一种简单直观的排序算法。它的工作原理是通过构建有序序列#xff0c;对于未排序数据#xff0c;在已排序序列中从后向前扫描#xff0c;找到相应位置并插入。插入排序在实现上#xff0c;在从…插入排序
插入排序英语Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
插入排序分析 def insert_sort(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]alist [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)时间复杂度
最优时间复杂度O(n)最坏时间复杂度O(n2)稳定性稳定 希尔排序 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DLShell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 希尔排序过程 希尔排序的基本思想是将数组列在一个表中并对列分别进行插入排序重复这过程不过每次用更长的列步长更长了列数更少了来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法算法本身还是使用数组进行排序。 例如假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]如果我们以步长为5开始进行排序我们可以通过将这列表放在有5列的表中来更好地描述算法这样他们就应该看起来是这样(竖着的元素是步长组成) 13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10然后我们对每列进行排序 10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45将上述四行数字依序接在一起时我们得到[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了然后再以3为步长进行排序 10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45排序之后变为 10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94最后以1步长进行排序此时就是简单的插入排序了 希尔排序的分析 def shell_sort(alist):n len(alist)# 初始步长gap n / 2while gap 0:# 按步长进行插入排序for i in range(gap, n):j i# 插入排序while jgap and alist[j-gap] alist[j]:alist[j-gap], alist[j] alist[j], alist[j-gap]j - gap# 得到新的步长gap gap / 2alist [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)时间复杂度 最优时间复杂度根据步长序列的不同而不同最坏时间复杂度O(n2)稳定性不稳定
