奇葩排序第二弹:)
从冒泡排序开始
先来看回顾一下冒泡排序的思想和原理.
冒泡排序的思想
冒泡排序的每一个元素都可以像小气泡一样, 根据自身大小, 一点一点向着数组的一侧移动.
冒泡排序算法的原理
比较相邻的元素. 如果第一个比第二个大, 就交换他们两个.
对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对. 这步做完后, 最后的元素会是最大的数.
针对所有的元素重复以上的步骤, 除了最后一个.
持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较.
一般情况下, 可以通过下面的动画理解冒泡排序.
现在我们来看一组特殊数据如果使用冒泡排序会怎么样.
将无序数列: 2,3,4,5,6,7,8,1, 使用冒泡排序使其从小到大排序.
进行逐步分析:
第一轮操作 ( 8 和 1 交换 )
第二轮操作 ( 7 和 1 交换 )
第三轮操作 ( 6 和 1 交换 )
第四轮操作 ( 5 和 1 交换 )
第五轮操作 ( 4 和 1 交换 )
第六轮操作 ( 3 和 1 交换 )
第七轮操作 ( 2 和 1 交换 )
仔细观察上面的这组无序数列, 实际上只有 1 的位置不在该在的位置, 而 2 ,3 ,4 ,5 ,6 ,7 ,8 都已经有序了, 结果使用冒泡排序, 需要 折腾 7 次 才能将 1 归位.
鸡尾酒排序
鸡尾酒排序, 也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序或快乐小时排序, 是冒泡排序的一种变形.
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序.
排序过程:
先对数组从左到右进行冒泡排序 (升序), 则最大的元素去到最右端
再对数组从右到左进行冒泡排序 (降序), 则最小的元素去到最左端
以此类推, 依次改变冒泡的方向, 并不断缩小未排序元素的范围, 直到最后一个元素结束
Show Me The Animation
第一轮操作 ( 8 和 1 交换 )
第二轮操作 ( 从序列右边开始遍历 )
第三轮操作 ( 从左向右比较和交换 )
在这一轮操作中, 没有元素位置交换, 证明已经有序, 排序结束.
对比 冒泡排序 , 鸡尾酒排序只需要 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 才开始真正的比较.
『 i = 1 』时, 比较 1 和 2 , 不交换, 只要不交换就自增 1 .
『 i = 2 』时, 比较 2 和 4 , 不交换, 只要不交换就自增 1 .
『 i = 3 』时, 比较 4 和 6 , 不交换, 只要不交换就自增 1 .
『 i = 4 』时, 表达式 ( i < n ) 不成立, 排序结束.
顺序输出为 [ 1 2 4 6 ].
地精排序算法代码
- template <class T>
- void gnome_sort_1(T data[], int n, bool comparator(T, T)){
- int i = 1;
- while (i <n){
- if (i> 0 && comparator(data[i], data[i-1])){
- swap(data[i], data[i-1]);
- i--;
- }else{
- i++;
- }
- }
- }
这种地精排序算法还有很多优化的空间, 这里小吴就不展开来讲了.
End
鸡尾酒排序和地精排序虽然被程序员小吴归为奇葩排序一类, 但是它们还是有一定的使用场景的.
在「大部分元素有序」的情况下, 使用鸡尾酒排序可以减少排序的回合数.
地精排序最著名的特点是代码只有一层循环, 在「大部分元素有序」的情况下, 可以减少排序回合数.
今日问题
除了鸡尾酒排序和地精排序以外, 你还知道哪些排序适合用于「大部分元素有序」的序列进行排序?
来源: https://juejin.im/post/5c37e5096fb9a049d05df191