插入排序算法解析 | 隔叶黄莺 Yanbin Blog

2020-04-27 | 阅读(464)

前面说过最原始的复杂度为 O(n²) 的冒泡和选择排序，也跳跃到了复杂度为 O(n log n) 的快速排序，现在又再看一个复杂度同样为 O(n²) 的插入排序。从排序名称结合代码我们理解了为什么叫做冒泡或是选择，快速排序自认高名，那么何以这又谓之插入排序呢？是怎么插入，从左边往右边插，还是从右边往左边插，这得搞清它的排序原理：

它在列表较低的一端维护一个有序的子列表(从最左端一个元素开始)，并逐个将每个新元素(高端的)"插入"这个子列表。插入的时候遍历低端列表，找准位置插入便是，插入点后的元素需后移，当所有高端的元素插入完成了，整个列表就变得有序了。

整个排序操作示意图如下：

好了，到此为止排序过程应该很清楚了，先不用看下面的代码，可以自己尝试写一段再进行对比。

我试了一段，如下：

items = [54, 26, 93, 17, 77, 31, 44, 55, 20]

for i in range(1, len(items)):
    for j in range(i):
        if items[i] < items[j]:
            items[i], items[j] = items[j], items[i]


print(items) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

items = [54, 26, 93, 17, 77, 31, 44, 55, 20]

for i in range(1, len(items)):

for j in range(i):

if items[i] < items[j]:

items[i], items[j] = items[j], items[i]

print(items) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

排序后结果是对的，但中间结果有些跳跃，可从下面看到每一步的变化(或点击链接在窗口中查看)

执行中的大循环演化过程是对的

[54, 26, 93, 17, 77, 31, 44, 55, 20]

[26, 54, 93, 17, 77, 31, 44, 55, 20]

[26, 54, 93, 17, 77, 31, 44, 55, 20]

[17, 26, 54, 93, 77, 31, 44, 55, 20]

[17, 26, 54, 77, 93, 31, 44, 55, 20]

[17, 26, 31, 54, 77, 93, 44, 55, 20]

[17, 26, 31, 44, 54, 77, 93, 55, 20]

[17, 26, 31, 44, 54, 55, 77, 93, 20]

[17, 20, 26, 31, 44, 54, 55, 77, 93]

如果要看每一步循环后的结果的话会有下面的中间状态：

[26, 54, 93, 17, 77, 31, 44, 55, 20]
[17, 54, 93, 26, 77, 31, 44, 55, 20]
[17, 26, 93, 54, 77, 31, 44, 55, 20]

插入 17 后，原本排好的 26 又跑到了 93 后面，插入 77 后 26 再一次回到了正确的位置上。也就是说插入结果后，插入点后方的元素并非整体后移，而且循环次数也较多。

正确的插入排序代码应该是这样子的：

def insertion_sort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index
        
        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position -1]
            position = position -1
            
        
        alist[position] = currentvalue
        

items = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertion_sort(items)

def insertion_sort(alist):

for index in range(1, len(alist)):

currentvalue = alist[index]

position = index

while position > 0 and alist[position-1] > currentvalue:

alist[position] = alist[position -1]

position = position -1

alist[position] = currentvalue

items = [54, 26, 93, 17, 77, 31, 44, 55, 20]

insertion_sort(items)

上面的插入排序代码插入时是在子列表中从后往前找，比当前元素大的后移，找到比当前元素小时，在该元素后插入当前元素。插入时也可以从左往右找位置，找到比当前元素小的时，在该位置前插入当前元素，剩下的子列表元素后移。交换操作的时间大约是移操作的 3 位，因为后都只需进行一次赋值。看下面的执行过程

或点击链接在新窗口中查看。

既然它的时间复杂度也是 O(n²)，那么它在某些方面有什么好处没？稳定，比冒泡，选择要快，对比一下分别对十万有序和无序列表的排序时间。就不与快速排序比较了，本身就是不公平的。

比较代码：

def bubble_sort(items):
    exchanges = True
    for i in range(len(items)):
        if not exchanges:
            return
        exchanges = False
        for j in range(len(items) - i - 1):
            if items[j] > items[j + 1]:
                exchanges = True
                items[j], items[j + 1] = items[j + 1], items[j]

def selection_sort(items):
    length = len(items)
    for i in range(length):
        for j in range(i + 1, length):
            if items[i] > items[j]:
                items[i], items[j] = items[j], items[i]


def insertion_sort(items):
    for index in range(1, len(items)):
        current_value = items[index]
        position = index

        while position > 0 and items[position - 1] > current_value:
            items[position] = items[position - 1]
            position = position - 1

        items[position] = current_value


from timeit import Timer
import random

t1 = Timer('bubble_sort(alist1)', 'from __main__ import bubble_sort', globals=globals())
t2 = Timer('selection_sort(alist2)', 'from __main__ import selection_sort', globals=globals())
t3 = Timer('insertion_sort(alist3)', 'from __main__ import insertion_sort', globals=globals())

length = 10000

times = 1
alist = list(range(length))
alist1 = list.copy(alist)
alist2 = list.copy(alist)
alist3 = list.copy(alist)
print(t1.timeit(number=times), t2.timeit(number=times), t3.timeit(number=times))

alist = random.sample(list(range(length)), length)
alist1 = list.copy(alist)
alist2 = list.copy(alist)
alist3 = list.copy(alist)
print(t1.timeit(number=times), t2.timeit(number=times), t3.timeit(number=times))

def bubble_sort(items):

exchanges = True

for i in range(len(items)):

if not exchanges:

return

exchanges = False

for j in range(len(items) - i - 1):

if items[j] > items[j + 1]:

exchanges = True

items[j], items[j + 1] = items[j + 1], items[j]

def selection_sort(items):

length = len(items)

for i in range(length):

for j in range(i + 1, length):

if items[i] > items[j]:

items[i], items[j] = items[j], items[i]

def insertion_sort(items):

for index in range(1, len(items)):

current_value = items[index]

position = index

while position > 0 and items[position - 1] > current_value:

items[position] = items[position - 1]

position = position - 1

items[position] = current_value

from timeit import Timer

import random

t1 = Timer('bubble_sort(alist1)', 'from __main__ import bubble_sort', globals=globals())

t2 = Timer('selection_sort(alist2)', 'from __main__ import selection_sort', globals=globals())

t3 = Timer('insertion_sort(alist3)', 'from __main__ import insertion_sort', globals=globals())

length = 10000

times = 1

alist = list(range(length))

alist1 = list.copy(alist)

alist2 = list.copy(alist)

alist3 = list.copy(alist)

print(t1.timeit(number=times), t2.timeit(number=times), t3.timeit(number=times))

alist = random.sample(list(range(length)), length)

alist1 = list.copy(alist)

alist2 = list.copy(alist)

alist3 = list.copy(alist)

print(t1.timeit(number=times), t2.timeit(number=times), t3.timeit(number=times))

排序有序/无序长度的列表的耗时

排序耗时(秒)	有序列表(1千)	有序列表(1万)	有序列表(10万）	无序列表(1千)	无序列表(1万)	无序列表(10万)
冒泡排序	0.000115519	0.000962132	0.010000855	0.084467821	9.189967045	930.12178294
选择排序	0.039573398	3.538418601	346.357997123	0.053535146	6.09890444	617.163237883
插入排序	0.000135626	0.00145926	0.017356704	0.044791698	5.156643332	519.60119013

插入排序也是对有序列表友好的，免去了移动元素的消耗。插入排序比选择要快的很大一方面是由于交换比逐个移动列表元素要快，但估计对于链接的排序又是另一回事了。更有序时，选择排序反而慢了，对于无序列表，冒泡效率低下，这三种排序方式相比而言，插入排序稍有些优势。对于同样是 O(n²) 复杂度的排序方式，减少元素的交换或移动的次数，或变交换为移动元素也能对效率有所提升。

接下来会有一种对插入排序的增强版本，Shell 排序，对列表跳跃方式分段进行插入排序，最后一次完整插入排序，目的也是减少了元素的移动次数而得以优化。

本文链接 https://yanbin.blog/insertion-sort-how-to/, 来自隔叶黄莺 Yanbin Blog

Perry Conn on Java 9 前/后使用 JAXB (包括支持 javax.* 或 jakarta.*)Your writing has a way of making even the most complex topics accessib...
Yanbin on Windows 安装使用 GCC(mingw-w64)是的，像 Rust 和 dotnet core 一样，都可以支持 Cross compile. Rust 和 g++ 在 Linux 下编译...
MerrickZ on Windows 安装使用 GCC(mingw-w64)我记得G++/GCC都是支持交叉编译的，你可以在linux/macos下面编译出windows平台的二进制PE文件……
Jack on 从 Rust 官方文档理解 Ownership哈哈，年纪大了才会下垂
Yanbin on unmi.cc 博客大事记谢谢再次光临，十来年前的回忆