请问为何第一段代码是插入排序第二段代码就是冒泡排序（ Python 实现）？
Newyorkcity · 2017-02-02 11:15:35 +08:00 · 1946 次点击这是一个创建于 2856 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 实现
我觉得这两个没啥子区别啊，最多就是第一个是从后向前比较每个相邻，而后一个是从前向后比较。。
另外冒泡排序和插入排序的区别到底在于何处呢？谢谢
第 1 条附言 · 2017-02-02 12:06:07 +08:00
其实我感到最困惑的地方是为什么维基百科上给出的两段代码第一个是插入排序第二个是冒泡排序。
我觉得第一段不是插入排序。
我觉得第一段不是插入排序。
 |
1
Andiry 2017-02-02 11:27:02 +08:00
差别在于对于已排序序列，冒泡是 n2 次比较，插入只是 n 次
|
 |
2
czheo 2017-02-02 11:36:48 +08:00
|
 |
3
Newyorkcity OP |
 |
4
binux 2017-02-02 12:11:28 +08:00
第一段代码是插入排序，只不过因为第一个的 lst 不是链表，无法做到真正的插入，只能通过位移实现。不过你要把它理解为冒泡，也不是不可以，名字又不重要。
|
|
5
czheo 2017-02-02 13:24:05 +08:00  1
wiki 的也算。但不是经典的，写的也不好。 1. insertion sort 不应该用 swap ， 2. j 的循环可以提前终止。
帮你写了一个经典的： https://gist.github.com/czheo/b872c8b7fc7b6ceb7a4f4952d5320749 |
|
6
Newyorkcity OP @binux 把它理解为冒泡也不是不可以？？冒泡和插入不是两个算法么？
|
|
7
czheo 2017-02-02 13:30:57 +08:00
冒泡的最大特点是用的 swap ，所以你要排序的 target 是一点一点像气泡一样“浮起来”的。
在我之前发的总结“ O(n2)排序”一章里面都提到了。 |
|
8
Newyorkcity OP @czheo 恩，插入排序比冒泡排序的复杂度小的原因就是在 29,30 行处，可以使得循环提前停止是吗？
|
|
9
czheo 2017-02-02 13:37:17 +08:00
@Newyorkcity 对的。还有一个是不用 swap ，所以更快。
|
|
10
binux 2017-02-02 13:58:29 +08:00
@Newyorkcity #6 看你怎么理解它
|
|
11
czheo 2017-02-02 15:32:24 +08:00
总结一下，冒泡和插入，都是把数组分成“排好”(sorted)的和“没有排好”(unsorted)的两部分，进行维护：每次从 unsorted 里面选一个数，放倒 sorted 里面。直到最后只剩下 sorted 的部分。
冒泡：左边 unsorted ，右边 sorted 。通过交换（ swap ）的方式，把 unsorted 里面最大的数，放倒 sorted 的开头。 插入：左边 sorted ，右边 unsorted 。把 unsorted 里面开头的数，插入到 sorted 里面合适的位置。 |
 |
12
limhiaoing 2017-02-02 15:43:16 +08:00
第 1 段严格来说不是插入排序，因为插入排序是稳定排序，通过 swap 交换无法保证稳定性，可以理解为不稳定的插入排序。
|
|
13
limhiaoing 2017-02-02 15:46:42 +08:00
代码看错了，忽略我上面的那段。。。
|
 |
14
xucheng 2017-02-02 18:07:10 +08:00 via iPad
插入排序和冒泡排序数学上是等价的
https://youtube.com/watch?v=pcJHkWwjNl4 |
Select Language