数据结构&算法实践—地精排序及改进

排序>>交换排序>>地精排序

List:

  1. start

基本概念:

维基百科:http://en.wikipedia.org/wiki/Gnome_sort(目前只有英文版的)

地精排序又称侏儒排序,类似于插入排序,但是将一个数放入其正确位置的交换同冒泡排序(一系列交换)

简单,只有一层循环,

时间复杂度O(n^2),最优复杂度O(n),平均时间复杂度O(n^2)

其实思想很简单,往前冒泡,一旦发生数据交换,就往回冒泡,直到把被交换数字放入正确位置,之后,继续前进

伪代码(来自于维基百科)

例子:

1 start

  1. start

观察上面例子,是不是发现有些别扭…….

没错,若是到了b存在交换,反向冒泡,直至把被交换数冒泡放到其有序位置a,然后再从a->b进行比较冒泡

其实,a->b这一段序列已经是有序的,不需要浪费比较次数在这上面

所以我们进行jump

即,记录b的位置,当发现反序冒泡没有交换时(冒泡结束),jump到b位置,继续正序冒泡

代码:

实际过程:

cmp 5 3

cmp 5 2

cmp 3 2

jump 2
cmp 3 5
cmp 5 4

cmp 3 4
jump 4

相同例子的序列,改进前比较次数12,改进后只需要9次

  1. start

A.地精排序概念,过程描述?

B.时间复杂度?空间复杂度?是否是稳定排序?

C.适用场景,何种情况下表现最优

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 3 收藏 评论

关于作者:wklken

Pythonista/vimer 个人主页 · 我的文章 · 37 ·   

可能感兴趣的话题



直接登录
跳到底部
返回顶部