【在厨房想30天的演算法】Day 16 演算法 : 排序 sort III 希尔、摇晃、基数

Aloha！又是我少女人妻 Uerica ～ 我每天看到时间快接近午夜 12 点，都能感受到灰姑娘的慌张，仙杜瑞拉跟王子跳舞到一半急急忙忙地跑回家，是因为她还没发铁人赛文章！

希尔排序法 Shell Sort

又称 递减增量排序法 diminishing increment sort。希尔排序法是插入排序法 insertion Sort 的改良版，前面提过，插入排序法用在排序完全是乱数的元素效率是很低的，所以用此方法来解决。

延伸阅读：Day 14 排序 sort 演算法 I : 介绍、气泡、选择、插入

希尔排序法的作法是由大到小选择数个间距 Gap，资料依据选择的间距将元素分组，分别进行插入排序，反覆操作直到最後一个间距为 1 为止，间距的选择对执行效率会有很大的影响。

常见的 Gap

• Shell 原本的 Gap：N/2、N/4、...1 (N为数列长度)
• Hibbard 的 Gap：1、3、7、...、2k-1
• Knuth 的 Gap: 1、4、13、...、(3k - 1) / 2
• Sedgewick 的 Gap: 1、5、19、41、109...

希尔排序法 Shell Sort 操作图解

• 首先取一个未排序数列，数列元素有 8 个 (N = 8) ，第一次排序的 Gap 取 N/2 = 8/2 = 4。
  

• 因 Gap 是 4，表示每四个为一组相互比较，所以第 0 个与第 4 个元素比较并排序。
  

• 比较後发现因 56 大於 12，所以 12 与 56 交换位置。
  

• 结束後，继续下一组元素的比较，比较第 1 个与第 5 个元素，因 1 小於 49 所以位置不变。
  

• 再继续下一组元素的比较，因 33 大於 20 ，所以 20 与 33 交换位置。
  
  

• 结束後，再继续下一组元素的比较，因 7 小於 51 所以位置不变。已经比较到最後一个元素，所以第一回合结束。
  

• 结束第一回合後，将 Gap 缩小，此时 Gap 取 N/4 = 8/4 = 2，表示每两个为一组比较。如下图，第 0 个与第 2 个比较，因 12 小於 20 所以维持不变。
  

• 再下一组， 1 小於 7 ，所以维持不变。
  

• 再下一组， 20 小於 56 ，所以维持不变。
  

• 再下一组， 7 小於 49 ，所以维持不变。
  

• 再下一组， 56 大於 33 ，所以将 33 与 56 交换位置，如同插入排序法，往前插入後，要再比较前一个位置的元素，如下图因 20 小於 33 ，所以维持不变。
  
  
  

• 再回来比较下一组元素，因 49 小於 51 所以维持不变。比较到最後一个元素，所以第二回合结束。
  

• 再将 Gap 缩小至 1 ，表示邻近的两个元素为一组互相做比较并排序。如下图第 0 个与第 1 个位置做比较。因 12 大於 1 ，所以 1 与 12 交换位置。
  
  

• 再比较下一组元素，12 小於 20，所以位置维持不变
  

• 再比较下一组元素，20 大於 7 所以位置交换。交换後如同插入排序法，7要再往前一个元素比较，因 12 大於 7，所以 7 再与 12 交换。7 再往前一个元素比较，因 1 小於 7 所以维持不变。
  
  
  
  

• 再比较下一组元素...
  
  
  

• 因 56 大於 51 ，所以需交换位置。交换後需再往前比较，因 49 小於 51 所以维持不变。
  
  
  

• 将啷～这样整个希尔排序法就完成啦！484 很简单啊！
  

双向气泡排序法 Bidirectional Bubble Sort

又称 摇晃排序法 Shaker Sort、鸡尾酒排序法Cocktail Sort，在这边我使用双气泡排序这个名称较为好懂，顾名思义就是气泡排序法的改良版，原本的气泡排序法只从一个方向做比对，而双向气泡排序法则是两边来回反覆操作，直到排序完成为止。

延伸阅读：Day 14 排序 sort 演算法 I : 介绍、气泡、选择、插入

双向气泡排序法 Bidirectional Bubble Sort 操作图解

• 首先取一个未排序元素数列如下
  

• 跟气泡排序法一样，先由右往左开始两两比对。若左边元素小於右边元素位置不变。
  
  

• 若左边元素大於右边元素则两两交换。下图 3 大於 1 ，所以两元素交换。
  
  

• 继续向前比对，因 5 大於 1 ，所以两元素交换。
  
  

• 最小值已排序到最左边，第一回合结束。
  

• 与气泡排序法不同之处，第二回合由左往右开始。若左边元素大於右边元素则做交换。因 5 大於 3 ，所以两两交换。
  
  

• 因 5 大於 2 ，所以两两交换。
  
  

• 因 5 大於 4 ，所以两两交换。
  
  

• 此时最大值已排到最右边，第二回合结束
  

• 此时再从右往左开始比对，左边元素小於右边元素位置不变。
  

• 若左边元素大於右边元素则两两交换，因 3 大於 2 ，所以两元素交换。
  
  

• 第三回合结束！排序就完成了，比原本的气泡排序法省了很多时间呢！
  

基数排序 Radix Sort

基数排序法与前面的排序法不同，基数排序法不用通过元素相互比较来做排序，且可用在多键值的元素排序，如两个键值 (1,2)、(2,4)、(3,2)，或扑克牌 (梅花,3)、(方块,7)等，属於较为特殊的排序法。

基数排序法是用桶子 Bucket 来将元素分类，并依照每个位数来做排序，元素的基底为多少就需准备多少个桶，若元素为数值，基底则为进制。例如 10 进位的数值则准备 10 个桶子，16 进位则是 16 个桶子，以此类推。

依照位数排序的先後顺序，可分为两种：

• LSD Least significant digit：小位数排到大。
• MSD Most significant digit：最大位数排到小。

参考资料:

Rust Algorithm Club

[演算法] 排序演算法(Sort Algorithm)

维基百科: 排序演算法

好的～～感谢阅读！大家掰掰明天见啦！再不发文我的马车也要变南瓜跟老鼠了！