python排序算法 直接插入排序法和折半插入排序法

发布时间:2023年12月17日

最近需要使用到一些排序算法,今天主要使针对直接插入排序和折半插入排序进行讲解。

首先是直接插入排序,其排序过程主要是,针对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 - 1
        while j >= 0 and key < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums

A = [60, 30, 80, 19],对A集合使用直接排序后的输出结果

然后就是折半插入排序,其主要是为了降低直接插入排序法的时间复杂度,对直接插入进行了一定的改进,减少插入过程中的比较次数,其实现主要是使用双指针的方式,low和high指针,这两个指针指向有序子集合的头和尾,然后取(low+high)/2的向下取整即是mid,根据每次与mid指向的值对比,如果大于这个值,则这个值应该在mid与high之间,如果小于这个值,则该值应该在mid和low之间。折半插入的实现如下:

def halfSort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        high = i - 1
        low = 0
        while (low <= high):
            mid = int((low + high) / 2)
            if (key >= nums[mid]):
                low = mid + 1
            if (key <= nums[mid]):
                high = mid - 1
        j = i - 1
        while (j >= low):
            nums[j + 1] = nums[j]
            j -= 1
        nums[low] = key
    return nums

B=[20,30,90,10,28,49,20,41,42,78],对B进行折半插入排序之后的输出结果

以上就是两个排序的实现方法。

文章来源:https://blog.csdn.net/Mrsawyer/article/details/135051429
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。