百度网站风格,少儿编程收费价目表,店面设计效果图大全,河南移动官网网站建设最近需要使用到一些排序算法#xff0c;今天主要使针对直接插入排序和折半插入排序进行讲解。
首先是直接插入排序#xff0c;其排序过程主要是#xff0c;针对A[a1,a2,a3,a4,a5....an]#xff0c;从排序的序列头部起始位置开始#xff0c;将其也就是a1视为只有一个元素的…最近需要使用到一些排序算法今天主要使针对直接插入排序和折半插入排序进行讲解。
首先是直接插入排序其排序过程主要是针对A[a1,a2,a3,a4,a5....an]从排序的序列头部起始位置开始将其也就是a1视为只有一个元素的子集合B[a1]这个B子集合本身就是有序的。
然后从a1之后的所有元素也就是从a2开始每次将a2到an按照正序或者倒序的方式插入到有序的这个B子集合中去这样最终能够得到包含所有A集合的元素的B集合这也就是最后的有序的A集合。 添加图片注释不超过 140 字可选
示意图如上对应的A集合和B集合每次循环B集合增加一个元素最后就得到正序的A集合。
直接排序的python实现如下
def quickSort(nums):for i in range(1, len(nums)):key nums[i]j i - 1while j 0 and key nums[j]:nums[j 1] nums[j]j - 1nums[j 1] keyreturn nums A [60, 30, 80, 19]对A集合使用直接排序后的输出结果
然后就是折半插入排序其主要是为了降低直接插入排序法的时间复杂度对直接插入进行了一定的改进减少插入过程中的比较次数其实现主要是使用双指针的方式low和high指针这两个指针指向有序子集合的头和尾然后取lowhigh/2的向下取整即是mid根据每次与mid指向的值对比如果大于这个值则这个值应该在mid与high之间如果小于这个值则该值应该在mid和low之间。折半插入的实现如下
def halfSort(nums):for i in range(1, len(nums)):key nums[i]high i - 1low 0while (low high):mid int((low high) / 2)if (key nums[mid]):low mid 1if (key nums[mid]):high mid - 1j i - 1while (j low):nums[j 1] nums[j]j - 1nums[low] keyreturn nums B[20,30,90,10,28,49,20,41,42,78]对B进行折半插入排序之后的输出结果
以上就是两个排序的实现方法。
