Python3排序算法03 - 插入排序

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1415 次阅读

Synopsis: 插入排序是一种简单直观的排序算法,它的工作原理非常类似于我们抓扑克牌,对于未排序数据(右手抓到的牌),在已排序序列(左手已经排好序的手牌)中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place sorting,即只需用到 O(1) 的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 算法介绍

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序序列中的某个数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

抓扑克牌

算法(假设按升序排序)的主要步骤如下:

  1. 将初始未排序序列的第1个元素当作一个已排序序列,把第2个元素到最后一个元素当作未排序序列
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入已排序序列的适当位置(从后向前扫描已排序序列)。如果待插入的元素与已排序序列中的某个元素相等,则将待插入的元素插入到相等元素的后面

Insertion Sort 01

2. Python实现

Insertion Sort 02

2.1 算法1

相当于将 L[i] 与 "已排序序列" 中的元素(从后向前)依次比较,如果 L[i] 比较小,则交换位置。使用 while 循环和元组解包(Tuple Unpacking) 就地交换两个元素的值:

def insertion_sort(L):
    '''插入排序,升序
    相当于将L[i]与 "已排序序列" 中的元素(从后向前)依次比较,如果L[i]比较小,则交换位置
    '''
    n = len(L)
    if n <= 1:
        return

    # 首先,假设第1个元素L[0]是 "已排序序列",第2个元素L[1]至最后一个元素L[n-1]是 "未排序序列"
    for i in range(1, n):  # 未排序的元素有 n-1 个,所以共需要 n-1 次插入操作。 i 表示 "未排序序列" 的第1个元素的下标,所以 i 从下标 1 开始

        # 将 "未排序序列" 的第1个元素和 "已排序序列" 从后向前,每两个元素之间比较,如果顺序不对就交换它俩的位置
        # 使用while循环
        j = i
        # j >= 1是因为后续j[j-1],否则下标越界
        while j >= 1 and L[j] < L[j-1]:  # 第1次是比较 "未排序序列" 的第1个元素和 "已排序序列" 的最后1个元素
            L[j], L[j-1] = L[j-1], L[j]
            j -= 1


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    insertion_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试:

from timeit import timeit


def insertion_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    for i in range(1, n):
        j = i
        while j >= 1 and L[j] < L[j-1]:
            L[j], L[j-1] = L
                                
                            
  • ppiero
  • Madman
  • dima1901065l
  • stevenszhou20
  • haoyu36
  • 阿狸的文献
  • 费袆
  • Peter-haotian-cui
  • nnlxin
  • 794754074
  • 十一
  • Jie Yang
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法03 - 插入排序

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.