一个看上去是bug却是正确插入排序变种

发表评论

A+

看到一个有意思的排序算法，一开始看上去像是冒泡排序写错了。但实际上却是正确的排序算法，做个分析。文章链接
本质上是一个插入排序算法

算法

算法介绍

未知排序算法

不知道这个什么语言，但逻辑是清楚的。
从文章中得知，这是一个升序排序算法。

for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]

冒泡排序算法

因为写法和冒泡排序比较像，所以先和冒泡排序比较。

for i = 1 to n do
for j = i + 1 to n do
if A[i] > A[j] then
swap A[i] and A[j]

对比

二者都是两个循环的算法，复杂度都是O(n²)，主要的差异点在于：
1. 冒泡排序在第二个循环中，起始未知是i，而不是1.
2. 需要交换的判断条件二者相反。

看到这里，隐隐约约会感觉未知算法可能正好是负负得正了。

测试

用python测试这个逻辑

不知道原始算法用的什么语言，所以用python代码重写，顺便将排序过程打印出来，这样利于搞清楚算法的本质。
可以用在线环境运行一下。

#A=[1,2,3,4,5,6]
#A=[6,5,4,3,2,1]
#A=[2,3,4,1,2,3]
A=[1,2,3,4,5,0]
n=len(A)

def print_list(a,i,j):
    print("[",end="")
    for idx,x in enumerate(a):
        if idx==i:
            print("<"+str(x)+">",end='')
        elif idx==j:
            print("("+str(x)+")",end='')
        else:
            print(x,end='')
        print(",",end='')
    print("]")

print(A)
js=0
for i in range(n):
    for j in range(n):
        js+=1
        print("number:%d,i:%d,j:%d " %(js,i,j),end="\n")
        if j>=i:
            break    # 此处可减少部分无用的循环
            pass     # 方便调试

        # 比较大小并交换
        if A[i]<A[j]:

            print_list(A,i,j)

            tp=A[i]
            A[i]=A[j]
            A[j]=tp

            print_list(A,j,i)

print(A)

执行输出

这里的输出信息可以清楚的看出元素是如何交换的。
A=[1, 2, 3, 4, 5, 0]，这个数据比较特殊，数组本身就是有序的，但最小值在末尾。

[1, 2, 3, 4, 5, 0]
number:1,i:0,j:0 
number:2,i:1,j:0 
number:3,i:1,j:1 
number:4,i:2,j:0 
number:5,i:2,j:1 
number:6,i:2,j:2 
number:7,i:3,j:0 
number:8,i:3,j:1 
number:9,i:3,j:2 
number:10,i:3,j:3 
number:11,i:4,j:0 
number:12,i:4,j:1 
number:13,i:4,j:2 
number:14,i:4,j:3 
number:15,i:4,j:4 
number:16,i:5,j:0 
[(1),2,3,4,5,<0>,]
[<0>,2,3,4,5,(1),]
number:17,i:5,j:1 
[0,(2),3,4,5,<1>,]
[0,<1>,3,4,5,(2),]
number:18,i:5,j:2 
[0,1,(3),4,5,<2>,]
[0,1,<2>,4,5,(3),]
number:19,i:5,j:3 
[0,1,2,(4),5,<3>,]
[0,1,2,<3>,5,(4),]
number:20,i:5,j:4 
[0,1,2,3,(5),<4>,]
[0,1,2,3,<4>,(5),]
number:21,i:5,j:5 
[0, 1, 2, 3, 4, 5]

分析

未知算法的特点

因为是if A[i]<A[j],所以大循环中的i指向的值，在每一次小循环运行完后，必然是最大值。
小循环和大循环的扫描顺序是一样的，都是从左往右。

猜想

根据算法流程分析，可以得出这样的猜测：
1. 小循环时，对元素有效的操作范围是[0,i)，因为大循环是从左往右的，最后一次循环i==n-1后，就结束了。
2. 如果列表[0,i)本身是有序的，则小循环执行后，依然是有序的。

关键

然后我们需要证明这个猜想。
原文是用了数学归纳法来证明，不过这里不写这么复杂，只挑几个关键点。
1. 只需要确认第二个猜想是正确的就可以了。
2. 此时的逻辑已经基本和插入排序一样了，如果是插入排序算法，就无须专门证明了。

未知算法的本质是插入排序算法

插入排序算法

插入排序算法图示。
1. 插入排序的目的是维护左边的数组有序。
2. 算法从左到右扫描元素，将元素插入到有序的数组中。

差异

常见的插入排序，在大循环扫描的时候。
1. 先找到插入点
2. 将后面的元素后移。

在后移元素的环节，是不需要再比较的。未知算法从头到尾都有比较的动作，造成了误导，容易往冒泡排序靠。
此外，常见的插入排序中，查找插入点通常会从后往前扫描或使用二分查找，未知算法是从前往后扫描，并把查找插入点和元素后移一块做了。

优化

因为对元素有效的操作范围是[0,i)，所以小循环j>=i时，可以结束。
第二个循环可以做下改动，变成插入排序。不过这样代码就不那么简洁了。

总结

所以，这个未知算法其实是插入排序的一种变种写法。但是会多一倍赋值动作和一些无用的比较。
在不考虑排序性能的时候，是个不错的实现。

算法