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

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

首先是直接插入排序，其排序过程主要是，针对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