请问为何第一段代码是插入排序第二段代码就是冒泡排序（ 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.