请问为何第一段代码是插入排序第二段代码就是冒泡排序（ Python 实现）？

[Newyorkcity]

def insert_sort(lst):
    n=len(lst)
    if n==1: return lst
    for i in range(1,n):
        for j in range(i,0,-1):
            if lst[j]<lst[j-1]: lst[j],lst[j-1]=lst[j-1],lst[j]
    return lst

以上来自插入排序的维基百科中的 python 实现

def bubble(List):
    for j in range(len(List)-1,0,-1):
        for i in range(0, j):
            if List[i] > List[i+1]:
                List[i], List[i+1] = List[i+1], List[i]
    return List

这个来自冒泡排序的维基百科中的 python 实现

---

我觉得这两个没啥子区别啊，最多就是第一个是从后向前比较每个相邻，而后一个是从前向后比较。。
另外冒泡排序和插入排序的区别到底在于何处呢？谢谢

[Andiry]

差别在于对于已排序序列，冒泡是 n2 次比较，插入只是 n 次

[czheo]

可以参考这个总结。 https://medium.com/@czheo/排序-b5ef06533b11

[Newyorkcity]

@Andiry
@czheo
能帮忙看看第一段代码是不是插入排序吗？谢谢

[binux]

第一段代码是插入排序，只不过因为第一个的 lst 不是链表，无法做到真正的插入，只能通过位移实现。不过你要把它理解为冒泡，也不是不可以，名字又不重要。

[czheo]

wiki 的也算。但不是经典的，写的也不好。 1. insertion sort 不应该用 swap ， 2. j 的循环可以提前终止。

帮你写了一个经典的：
https://gist.github.com/czheo/b872c8b7fc7b6ceb7a4f4952d5320749

[Newyorkcity]

@binux 把它理解为冒泡也不是不可以？？冒泡和插入不是两个算法么？

[czheo]

冒泡的最大特点是用的 swap ，所以你要排序的 target 是一点一点像气泡一样“浮起来”的。
在我之前发的总结“ O(n2)排序”一章里面都提到了。

[Newyorkcity]

@czheo 恩，插入排序比冒泡排序的复杂度小的原因就是在 29,30 行处，可以使得循环提前停止是吗？

[czheo]

@Newyorkcity 对的。还有一个是不用 swap ，所以更快。

[binux]

@Newyorkcity #6 看你怎么理解它

[czheo]

总结一下，冒泡和插入，都是把数组分成“排好”(sorted)的和“没有排好”(unsorted)的两部分，进行维护：每次从 unsorted 里面选一个数，放倒 sorted 里面。直到最后只剩下 sorted 的部分。
冒泡：左边 unsorted ，右边 sorted 。通过交换（ swap ）的方式，把 unsorted 里面最大的数，放倒 sorted 的开头。
插入：左边 sorted ，右边 unsorted 。把 unsorted 里面开头的数，插入到 sorted 里面合适的位置。

[limhiaoing]

第 1 段严格来说不是插入排序，因为插入排序是稳定排序，通过 swap 交换无法保证稳定性，可以理解为不稳定的插入排序。

[limhiaoing]

代码看错了，忽略我上面的那段。。。

[xucheng]

插入排序和冒泡排序数学上是等价的
https://youtube.com/watch?v=pcJHkWwjNl4

[czheo]

@xucheng thx for sharing. but your video is talking about selection vs insertion sort, rather than bubble sort.