01.插入算法

插入排序

01.直接插入排序：

• 直接插入排序的原理：
  • 将序列分为已排序序列和未排序的序列。
    • 在未排序序列中，构建一个子排序序列，直至全部数据排序完成。
  • 将待排序的数，插入到已经排序的序列中合适的位置。
  • 增加一个哨兵，放入待比较的值，让它与后面已经排好的序列比较，找到合适的插入点。
• 直接插入排序的过程：

• 0为哨兵，1为已排序队列，9、8、5、6为未排序队列。

• 将未排序队列的第一个数9提取，放到哨兵的位置。
• 将哨兵9与已排序队列的最后一个数1比较，9比1大，则将9排序在1的后面。
• 1、9为已排序队列，8、5、6为未排序队列。

• 将未排序队列的第一个数8提取出来，放到哨兵的位置。
• 将哨兵8与已排序队列的最后一个数字9比较，8比9小，则9后退一位，8放在原来9的位置。
• 将哨兵8与已排序队列的最后第二个数字1比较，8比1大，则不移动位置。
• 1、8、9为已排序队列，5、6为未排序队列。

• 将未排序队列的第一个数5提取出来，放到哨兵的位置。
• 将哨兵5与已排序队列的最后一个数字9比较，5比9小，则9后退一位，5放在原来9的位置。
• 将哨兵5与已排序队列的最后第二个数字8比较，5比8小，则8后退一位，5放在原来8的位置。
• 将哨兵5与已排序队列的最后第三个数字1比较，5比1大，则不移动位置。
• 1、5、8、9为已排序序列，6为未排序序列。

• 将未排序队列的第一个数6提取出来，放到哨兵的位置。
• 将哨兵6与已排序队列的最后一个数字9比较，6比9小，则9后退一位，6放在原来9的位置。
• 将哨兵6与已排序队列的最后第二个数字8比较，6比8小，则8后退一位，6放在原来8的位置。
• 将哨兵6与已排序队列的最后第三个数字5比较，6比5大，则不移动位置。
• 1、5、6、8、9为已排序序列；无未排序序列。

02.直接插入排序的代码逻辑：

• 直接插入排序的代码实现：

def direct_insert_sort(x, y, *args):
    sorted_list = [x] + [y] + list(args)
    sentinel = 0
    length = len(sorted_list)

    for i in range(1, length):
        sentinel = sorted_list[i]

        j = i - 1
        if sorted_list[j] > sentinel:
            while sorted_list[j] > sentinel:
                sorted_list[j+1] = sorted_list[j]
                j = j - 1
            sorted_list[j+1] = sentinel
    print(sorted_list)


direct_insert_sort(4, 35, 33, 25, 8, 19, 152, 77)

• 直接插入排序的代码特性：
  • 最好的情况，正好是升序排列，比较迭代n-1次。
  • 最差的情况，最好是降序排列，比较迭代n(n-1)/2次。
  • 使用两层循环嵌套，时间复杂度O(n^2)。
  • 该算法较稳定，适合小规模数据比较的场景。
  • 如果数据量比较多，建议使用二分查找法来提高效率。

03.二分插入排序算法：

def insert(x, number):

    array = sorted(x)
    start = 0
    end = len(array) - 1
    middle = start + end // 2
    flag = True

    while flag:
        half = middle
        if number < array[start] or number > array[end]:
            half = start if number < array[start] else end + 1
            flag = False
        else:
            if array[half] <= number <= array[half + 1]:
                half += 1
                flag = False
            else:
                middle = (half + end) // 2 if number >= array[middle] else (start + half) // 2

    array.insert(half, number)
    return array


my_list = [100, 5, 55, 24, 67, 983, 35, 44, 32, 55]
do = insert(my_list, 14)
print(do)