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

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

算法

算法介绍

未知排序算法

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

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]

分析

未知算法的特点

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

猜想

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

关键

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

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

插入排序算法

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

差异

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

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

优化

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

总结

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

© 版权声明
THE END
广告
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情

    暂无评论内容