动画:什么是鸡尾酒排序和地精排序? (2)

第三轮操作 ( 从左向右比较和交换 )

第三轮操作 ( 从左向右比较和交换 )

第三轮操作 ( 从左向右比较和交换 )
在这一轮操作中,没有元素位置交换,证明已经有序,排序结束。

对比 冒泡排序 ,鸡尾酒排序只需要 3 轮操作就可以完成排序。

地精排序

Gnome 排序(地精排序),起初由 Hamid Sarbazi-Azad 于 2000 年提出,并被称为 stupid 排序,后来被 Dick Grune 描述并命名为 “地精排序” 。

地精排序和插入排序类似,除了移动一个元素到最终的位置,是通过交换一系列的元素实现,就像冒泡排序一样。概念上十分简单,不需要嵌套循环。时间复杂度为O(n2),但是如果初始数列基本有序,时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。平均运行时间为O(n^2)。

将无序数列:6,2,4,1,5,使用地精排序使其从小到大排序。

通过设计标识 i = 0 ,然后从头开始判断,什么时候 ( i < 4 ) 不成立,什么时候排序结束。

这里的核心点就是 如何控制 i 的值

第一轮操作「i = 0」

动画:什么是鸡尾酒排序和地精排序?

先让 i 自增 1 ,达到值为 1 才开始比较 :

交换前 [ 6 2 4 1 ] 『 i = 0

交换后 [ 6 2 4 1 ] 『 i = 1

第二轮操作「i = 1」

动画:什么是鸡尾酒排序和地精排序?

比较 6 和 2 ,发生交换,只要发生交换 i 就减 1

交换前 [ 6 2 4 1 ]『 i = 1 』

交换后 [ 2 6 4 1 ]『 i = 0 』

第三轮操作「i = 0」

动画:什么是鸡尾酒排序和地精排序?

i 变成 0 了,啥也不干,自增变成 1 再说。

交换前 [ 2 6 4 1 ]『 i = 0 』

交换后 [ 2 6 4 1 ]『 i = 1 』

第四轮操作「i = 1」

动画:什么是鸡尾酒排序和地精排序?

比较 2 和 6 ,不交换,只要不要换就自增 1

交换前 [ 2 6 4 1 ]『 i = 1 』

交换后 [ 2 6 4 1 ]『 i = 2 』

第五轮操作「i = 2」

动画:什么是鸡尾酒排序和地精排序?

比较 6 和 4 ,发生交换,只要发生交换 i 就减 1

交换前 [ 2 6 4 1 ]『 i = 2 』

交换后 [ 2 4 6 1 ]『 i = 1 』

第六轮操作「i = 1」

动画:什么是鸡尾酒排序和地精排序?

比较 2 和 4 ,不交换,只要不要换就自增 1

交换前 [ 2 6 4 1 ]『 i = 1 』

交换后 [ 2 4 6 1 ]『 i = 2 』

第七轮操作「i = 2」

动画:什么是鸡尾酒排序和地精排序?

比较 4 和 6 ,不交换,只要不要换就自增 1

交换前 [ 2 4 6 1 ]『 i = 2 』

交换后 [ 2 4 6 1 ]『 i = 3 』

第八轮操作「i = 3」

动画:什么是鸡尾酒排序和地精排序?

比较 6 和 1 ,发生交换,只要发生交换 i 就减 1

交换前 [ 2 4 6 1 ]『 i = 3 』

交换后 [ 2 4 1 6 ]『 i = 2 』

第九轮操作「i = 2」

动画:什么是鸡尾酒排序和地精排序?

比较 4 和 1 ,发生交换,只要发生交换 i 就减 1

交换前 [ 2 4 1 6 ]『 i = 2 』

交换后 [ 2 1 4 6 ]『 i = 1 』

第十轮操作「i = 1」

动画:什么是鸡尾酒排序和地精排序?

比较 2 和 1 ,发生交换,只要发生交换 i 就减 1

交换前 [ 2 1 4 6 ]『 i = 1 』

交换后 [ 1 2 4 6 ]『 i = 0 』

第十一轮操作「i = 0」

动画:什么是鸡尾酒排序和地精排序?

啥也不干,先让 i 自增1,达到值为 1 才开始真正的比较。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsszdp.html