[数据结构与算法]【MOOC】简单排序——冒泡、插入

1万个数据以上的排序?

?一、冒泡排序

一趟排序：

从上到下，交换相邻的元素

一趟排序结束可以保证：最下面的元素一定是本趟中最大的

下一趟排序从开头到倒数第二个元素为止

共N-1趟

?

?当中途就有序了，之后的比较动作就很多余

可以使用标记，当中途就有序就退出

?

当所有元素放在一个单向链表里，

冒泡排序仍然可行（单向的扫描和交换）

?只有当下一元素严格大于上一元素时，才做交换；

冒泡排序是稳定的。

?

?

?二、插入排序

1.摸新牌

2.从最后一张牌开始比较，新牌小则移位

3.新牌落位

?

三、时间复杂度下界

冒泡排序和选择排序具有公共的时间复杂度下界。

?插入排序的时间复杂度与N有关，且与逆序对数有关

O(a*N+b*I)~O(N+I)

?

?

关注博主即可阅读全文