当前课程知识点:数据结构(下) > 第十二章 排序 > (c1) 希尔排序:Shell序列 > 12c1-2: 实例
考察这个由13个整数所构成的
待排序序列
采用希尔排序算法
我们首先将矩阵的宽度取作8
于是我们按照不超过8个元素为准则
将整个序列分为两段
而每一段都对应于矩阵的一行
这样我们就得到了一个宽度为8的矩阵
接下来我们对这个矩阵逐列排序
很容易验证第一列的排序结果是这样
第二列是这样
第三列是这样
第四列是这样
以及第五列是这样
最后三列是退化的情况
直接得到排序的结果
至此我们已经完成了
对应于宽度8的一趟sorting
在转换为新的矩阵之前
我们需要将它重新复原为
一个线性的序列
具体来说与刚才构成矩阵的操作
完全相反
我们这时候需要将矩阵的每一行
逐个取出
并依次串接
从而构成一个线性序列
我们接下来采用的矩阵宽度为五
因此我们接下来要以五为单位
将此序列切分为若干段
而每一段都将作为新矩阵的一行
接下来我们依然需要逐列排序
不难验证这是第一列的排序结果
这是第二列的排序结果
以及第三列第四列第五列的排序结果
一旦完成了这样的逐列排序
我们又需要在逻辑上
将这个矩阵重新恢复为一个序列
具体的方法
依然与刚才构造矩阵的过程相反
也就是说我们需要将矩阵中的每一行
逐个取出并依次串接
从而还原为一个线性的序列
此时我们不妨稍作停留
来观察一下这两个中间结果
虽然我们现在还不能精确的度量
但是我们依然能够隐约
而切实的感觉到
整个序列的有序性
是在不断的改善
那么接下来还会继续改善吗
我们不妨继续下去
再接下来的一步
我们将矩阵的宽度取作三
也就是说我们将以每三个元素为单位
将整个序列分割成若干段
这些段也就分别构成了新矩阵的各行
这个新矩阵共有三列
我们接下来依然需要
对这个新矩阵中的三列分别排序
同样不难验证
各列分别排序的结果应该是这样
接下来我们依然需要逐行取出
所有的元素
并将它们依次串接起来
恢复为一个线性序列
至此你也不妨再次的大致体会一下
经过刚才的这样一趟逐列排序
整个序列的有序性又向前有所改进
为了再进一步的提高
整个序列的有序性
我们接下来将要采用的
矩阵宽度取作2
也就是说我们要以两个元素为单位
将整个序列切分成若干段
而且同样的每一段
都构成新矩阵的一行
此后我们又可以分别针对
这两列各做一次排序
不难验证排序的结果分别是这样
接下来同样的
我们又需要将这个矩阵中的元素
逐行取出
并将它们依次串接起来
恢复成为一个线性序列
请再次的体会一下
经过这样的一趟逐列排序
整个序列的有序性又有所改善
与所有的步长序列一样
我们最终也是终止于W1等于1
也就是说我们要将此时的线性序列
完整的视作为一列
并且对它进行排序
在经过了以上的各步之后
不出意外
我们的确得到了原序列的
一个排序结果
-选课之前
--写在选课之前
--宣传片
-考核方式
--考核方式
-OJ系统说明
--关于OJ
--1-注册与登录
--2-界面与选课
--3-提交测试
-关于课程教材与讲义
--课程教材与讲义
-关于讨论区
--关于讨论区
-微信平台
--html
-PA晋级申请
--PA晋级
-(a)概述
--07A-1 纵览
--07A-5 接口
-(a)概述--作业
-(b1)BST:查找
-第七章 二叉搜索树--(b1)BST:查找
-(b2)BST:插入
-(b2)BST:插入--作业
-(b3)BST:删除
-第七章 二叉搜索树--(b3)BST:删除
-(c)平衡与等价
-(c)平衡与等价--作业
-(d1)AVL树:重平衡
-第七章 二叉搜索树--(d1)AVL树:重平衡
-(d2)AVL树:插入
-(d2)AVL树:插入--作业
-(d3)AVL树:删除
-(d3)AVL树:删除--作业
-(d4)AVL树:(3+4)-重构
-(d4)AVL树:(3+4)-重构--作业
-本章测验
--章节测验
-(a1)伸展树:逐层伸展
--习题
-(a2)伸展树:双层伸展
--习题
-(a3)伸展树:算法实现
--习题
-(b1)B-树:动机
--习题
-(b2)B-树:结构
--习题
-(b3)B-树:查找
--习题
-(b4)B-树: 插入
--习题
-(b5)B-树: 删除
--习题
-(xa1)红黑树:动机
--习题
-(xa2)红黑树:结构
--习题
-(xa3)红黑树:插入
--习题
-(xa4)红黑树:删除
-本章测验
--习题
-(b)散列:原理
--09B-3 数组
--09B-4 原理
--09B-5 散列
--09B-6 冲突
--习题
-(c)散列:散列函数
--习题
-(d1)散列:排解冲突(1)
--习题
-(d2)散列:排解冲突(2)
--习题
-(e)桶/计数排序
--习题
-本章测验
--本章测试
-(a1)需求与动机
--习题
-(a2)基本实现
--习题
-(b1)完全二叉堆:结构
--习题
-(b2)完全二叉堆:插入与上滤
--习题
-(b3)完全二叉堆:删除与下滤
--习题
-(b4)完全二叉堆:批量建堆
--习题
-(c)堆排序
--习题
-(xa1)左式堆:结构
--习题
-(xa2)左式堆:合并
--习题
-(xa3)左式堆:插入与删除
-本章测验
--本章测试
-(a)ADT
--习题
-(b1)串匹配
--习题
-(b2)蛮力匹配
--习题
-(c1)KMP算法:从记忆力到预知力
--习题
-(c2)KMP算法:查询表
--习题
-(c3)KMP算法:理解next[]表
--习题
-(c4)KMP算法:构造next[]表
--习题
-(c5)KMP算法:分摊分析
--习题
-(c6)KMP算法:再改进
-(d1)BM_BC算法:以终为始
-(d2)BM_BC算法:坏字符
-(d3)BM_BC算法:构造bc[]
-(d4)BM_BC算法:性能分析
-(e1)BM_GS算法:好后缀
-(e2)BM_GS算法:构造gs表
-(e3)BM_GS算法:综合性能
-(f1)Karp-Rabin算法:串即是数
-(f2)Karp-Rabin算法:散列
-本章测验
--本章测试
-(a1)快速排序:算法A
-- 12a1-5: 实例
--习题
-(a2)快速排序:性能分析
--习题
-(a4)快速排序:变种
-(b1)选取:众数
-(b3)选取:通用算法
--习题
-(c1) 希尔排序:Shell序列
--习题
-(c2)希尔排序:逆序对
-本章测验
--本章测试