Python3排序算法03 - 插入排序

  • 原创
  • Madman
  • /
  • 2018-09-13 13:41
  • /
  • 0
  • 133 次阅读

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[j-1], L[j]
            j -= 1
    return L


print('Insertion sort function run 1000 times, cost: ', timeit('insertion_sort()', 'from __main__ import insertion_sort', number=1000), 'seconds.')

# Output:
# Insertion sort function run 1000 times, cost:  1.63546372 seconds.

2.2 算法2

跟算法1类似,使用 for 循环和元组解包(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个元素和 "已排序序列" 从后向前,每两个元素之间比较,如果顺序不对就交换它俩的位置
        # 所以,j 的范围是 [i, i-1,... 2, 1],即包含下标 i 和 "已排序序列" 的所有下标
        for j in range(i, 0, -1):  # 将 "未排序序列" 的第1个元素L[i],依次与 "已排序序列" 中的所有元素比较
            if L[j] < L[j-1]:  # 如果小于前一个元素,则交换位置
                L[j], L[j-1] = L[j-1], L[j]
            else:  # 如果不小于前一个元素,则肯定不小于这个元素之前的所有元素(因为前面已排好序了),所以可以退出比较的循环
                break


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):
        for j in range(i, 0, -1):
            if L[j] < L[j-1]:
                L[j], L[j-1] = L[j-1], L[j]
            else:
                break

    return L


print('Insertion sort function run 1000 times, cost: ', timeit('insertion_sort()', 'from __main__ import insertion_sort', number=1000), 'seconds.')

# Output:
# Insertion sort function run 1000 times, cost:  1.365289191 seconds.

2.3 算法3

相当于将 L[i] 提起来,再与 "已排序序列" 中的元素(从后向前)依次比较,如果 L[i] 比较小,则将 "已排序序列" 中的元素依次往后挪一个位置。使用 while 循环和临时变量 temp 交换两个元素的值:

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个元素(temp)提起来,再与 "已排序序列" 中的元素(从后向前)依次比较,
        # 如果 temp 小于 "已排序序列" 中的元素,则将 "已排序序列" 中的元素往后挪一位
        # 如果 temp 大于或等于 "已排序序列" 中的元素,则把 temp 插入该元素的后面
        temp = L[i]  # "未排序序列" 的第1个元素
        j = i
        # j >= 1是因为后续j[j-1],否则下标越界
        while j >= 1 and temp < L[j-1]:  # 如果 "未排序序列" 的第1个元素,小于 "已排序序列" 中的元素L[j]
            L[j] = L[j-1]  # 则将 "已排序序列" 中的元素L[j-1]的值复制给L[j],相当于L[j-1]向后挪了一个位置。第一次(j = i)时,会覆盖L[i],所以前面需要用temp先保存它
            j -= 1
        # 如果while条件为False:
        # 1. j < 1,则将 "未排序序列" 的第1个元素赋值给L[1]
        # 2. temp >= L[j-1],则将 "未排序序列" 的第1个元素 "插入" 到L[j-1]的后面(自己尝试 i=4 时,就知道了)
        L[j] = temp

        '''
        演示,第3次插入的过程:

        i = 3,此时列表为 [26, 54, 93, 17, 77, 31, 44, 55, 20],"已排序序列" 为[26, 54, 93],"未排序序列" 为[17, 77, 31, 44, 55, 20]
        temp = L[3]  # 17

        j = i  # j=3
        此时,while条件为True,L[j] = L[j-1],即L[3] = L[2] = 93,会覆盖之前的17,所以temp变量的作用就是先保留该值
        列表变为 [26, 54, 93, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=2
        此时,while条件为True,L[j] = L[j-1],即L[2] = L[1] = 54
        列表变为 [26, 54, 54, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=1
        此时,while条件为True,L[j] = L[j-1],即L[1] = L[0] = 26
        列表变为 [26, 26, 54, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=0
        此时,while条件为False,L[j] = temp,即L[0] = temp = 17
        列表变为 [17, 26, 54, 93, 77, 31, 44, 55, 20]
        至此,已将 "未排序序列" [17, 77, 31, 44, 55, 20] 的第1个元素17插入到 "已排序序列" [26, 54, 93] 的正确位置
        '''


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):
        temp = L[i]
        j = i
        while j >= 1 and temp < L[j-1]:
            L[j] = L[j-1]
            j -= 1
        L[j] = temp

    return L


print('Insertion sort function run 1000 times, cost: ', timeit('insertion_sort()', 'from __main__ import insertion_sort', number=1000), 'seconds.')

# Output:
# Insertion sort function run 1000 times, cost:  1.140121377 seconds.

3. 性能

3.1 时间复杂度

  • 最优时间复杂度: 需要O(n)次比较(comparisons),和O(1)次交换(swaps)。比如传入已经按 "升序" 排好序的列表,上述代码按 "升序" 去排列它
  • 最坏时间复杂度: 需要O(n^2)次比较,和O(n^2)次交换
  • 平均时间复杂度: 需要O(n^2)次比较,和O(n^2)次交换

3.2 空间复杂度

它是in-place comparison sort,总的空间复杂度(total)为O(n);还需要一个临时变量来交换元素位置,辅助空间复杂度(auxiliary)为O(1)

3.3 稳定性

选择排序稳定的排序算法

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法03 - 插入排序

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录