当前课程知识点:数据结构(下) >  第十二章 排序 >  (c1) 希尔排序:Shell序列 >  12c1-2: 实例

返回《数据结构(下)》慕课在线视频课程列表

12c1-2: 实例在线视频

12c1-2: 实例

下一节:12c1-3: 循秩访问

返回《数据结构(下)》慕课在线视频列表

12c1-2: 实例课程教案、知识点、字幕

考察这个由13个整数所构成的

待排序序列

采用希尔排序算法

我们首先将矩阵的宽度取作8

于是我们按照不超过8个元素为准则

将整个序列分为两段

而每一段都对应于矩阵的一行

这样我们就得到了一个宽度为8的矩阵

接下来我们对这个矩阵逐列排序

很容易验证第一列的排序结果是这样

第二列是这样

第三列是这样

第四列是这样

以及第五列是这样

最后三列是退化的情况

直接得到排序的结果

至此我们已经完成了

对应于宽度8的一趟sorting

在转换为新的矩阵之前

我们需要将它重新复原为

一个线性的序列

具体来说与刚才构成矩阵的操作

完全相反

我们这时候需要将矩阵的每一行

逐个取出

并依次串接

从而构成一个线性序列

我们接下来采用的矩阵宽度为五

因此我们接下来要以五为单位

将此序列切分为若干段

而每一段都将作为新矩阵的一行

接下来我们依然需要逐列排序

不难验证这是第一列的排序结果

这是第二列的排序结果

以及第三列第四列第五列的排序结果

一旦完成了这样的逐列排序

我们又需要在逻辑上

将这个矩阵重新恢复为一个序列

具体的方法

依然与刚才构造矩阵的过程相反

也就是说我们需要将矩阵中的每一行

逐个取出并依次串接

从而还原为一个线性的序列

此时我们不妨稍作停留

来观察一下这两个中间结果

虽然我们现在还不能精确的度量

但是我们依然能够隐约

而切实的感觉到

整个序列的有序性

是在不断的改善

那么接下来还会继续改善吗

我们不妨继续下去

再接下来的一步

我们将矩阵的宽度取作三

也就是说我们将以每三个元素为单位

将整个序列分割成若干段

这些段也就分别构成了新矩阵的各行

这个新矩阵共有三列

我们接下来依然需要

对这个新矩阵中的三列分别排序

同样不难验证

各列分别排序的结果应该是这样

接下来我们依然需要逐行取出

所有的元素

并将它们依次串接起来

恢复为一个线性序列

至此你也不妨再次的大致体会一下

经过刚才的这样一趟逐列排序

整个序列的有序性又向前有所改进

为了再进一步的提高

整个序列的有序性

我们接下来将要采用的

矩阵宽度取作2

也就是说我们要以两个元素为单位

将整个序列切分成若干段

而且同样的每一段

都构成新矩阵的一行

此后我们又可以分别针对

这两列各做一次排序

不难验证排序的结果分别是这样

接下来同样的

我们又需要将这个矩阵中的元素

逐行取出

并将它们依次串接起来

恢复成为一个线性序列

请再次的体会一下

经过这样的一趟逐列排序

整个序列的有序性又有所改善

与所有的步长序列一样

我们最终也是终止于W1等于1

也就是说我们要将此时的线性序列

完整的视作为一列

并且对它进行排序

在经过了以上的各步之后

不出意外

我们的确得到了原序列的

一个排序结果

数据结构(下)课程列表:

第零章

-选课之前

--写在选课之前

--宣传片

-考核方式

--考核方式

-OJ系统说明

--关于OJ

--1-注册与登录

--2-界面与选课

--3-提交测试

-关于课程教材与讲义

--课程教材与讲义

-关于讨论区

--关于讨论区

-微信平台

--html

-PA晋级申请

--PA晋级

--MOOC --> THU 晋级申请专区

--THU --> CST 晋级申请专区

--编程作业不过瘾?且来清华试比高!

第七章 二叉搜索树

-(a)概述

--07A-1 纵览

--07A-2 循关键码访问

--07A-3 有序性

--07A-4 单调性

--07A-5 接口

-(a)概述--作业

-(b1)BST:查找

--07B1-1 概述

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-第七章 二叉搜索树--(b1)BST:查找

-(b2)BST:插入

--07B2-1 插入:算法

--07B2-2 插入:实现

-(b2)BST:插入--作业

-(b3)BST:删除

--07B3-1 删除:框架

--07B3-2 删除:单分支

--07B3-3 删除:双分支

--07B3-4 删除:复杂度

-第七章 二叉搜索树--(b3)BST:删除

-(c)平衡与等价

--07C-1 极端退化

--07C-2 平均高度

--07C-3 理想+适度

--07C-4 歧义=等价

--07C-5 等价变换

-(c)平衡与等价--作业

-(d1)AVL树:重平衡

--07D1-1 AVL=BBST

--07D1-2 平衡因子

--07D1-3 适度平衡

--07D1-4 接口

--07D1-5 失衡+复衡

-第七章 二叉搜索树--(d1)AVL树:重平衡

-(d2)AVL树:插入

--07D2-1 插入:单旋

--07D2-2 插入:双旋

--07D2-3 插入:实现

-(d2)AVL树:插入--作业

-(d3)AVL树:删除

--07D3-1 删除:单旋

--07D3-2 删除:双旋

--07D3-3 删除:实现

-(d3)AVL树:删除--作业

-(d4)AVL树:(3+4)-重构

--07D4-1 ”3+4“重构

--07D4-2 ”3+4“实现

--07D4-3 rotateAt()

--07D4-4 综合评价

-(d4)AVL树:(3+4)-重构--作业

-本章测验

--章节测验

第八章 高级搜索树(上)

-(a1)伸展树:逐层伸展

--08A1-1 宽松平衡

--08A1-2 局部性

--08A1-3 自适应调整

--08A1-4 逐层伸展

--08A1-5 实例

--08A1-6 一步一步往上爬

--08A1-7 最坏情况

--习题

-(a2)伸展树:双层伸展

--08A2-1 双层伸展

--08A2-2 子孙异侧

--08A2-3 子孙同侧

--08A2-4 点睛之笔

--08A2-5 折叠效果

--08A2-6 分摊性能

--08A2-7 最后一步

--习题

-(a3)伸展树:算法实现

--08A3-1 功能接口

--08A3-2 伸展算法

--08A3-3 四种情况

--08A3-4 查找算法

--08A3-5 插入算法

--08A3-6 删除算法

--08A3-7 综合评价

--习题

-(b1)B-树:动机

--08B1-1 640KB

--08B1-2 越来越大的数据

--08B1-3 越来越小的内存

--08B1-4 一秒与一天

--08B1-5 分级I/O

--08B1-6 1B = 1KB

--习题

-(b2)B-树:结构

--08B2-1 观察体验

--08B2-2 多路平衡

--08B2-3 还是I/O

--08B2-4 深度统一

--08B2-5 阶次含义

--08b2-6: 紧凑表示

--08B2-7 BTNode

--08B2-8 BTree

--习题

-(b3)B-树:查找

--08B3-1 算法过程

--08B3-2 操作实例

--08B3-3 算法实现

--08B3-4 主次成本

--08B3-5 最大高度

--08B3-6 最小高度

--习题

第八章 高级搜索树(下)

-(b4)B-树: 插入

--08B4-1 算法框架

--08B4-2 分裂

--08B4-3 再分裂

--08B4-4 分裂到根

--08B4-5: 实例演示

--习题

-(b5)B-树: 删除

--08B5-1 算法框架

--08B5-2 旋转

--08B5-3 合并

--08B5-4 实例演示

--08B5-5 道法自然

--习题

-(xa1)红黑树:动机

--08XA1-1 观察体验

--08XA1-2 持久性

--08XA1-3 关联性

--08XA1-4 O(1)重构

--习题

-(xa2)红黑树:结构

--08XA2-1 定义规则

--08XA2-2 实例验证

--08XA2-3 提升变换

--08XA2-4 末端节点

--08XA2-5 红黒树,即是B-树

--08XA2-6 平衡性

--08xa2-7: 接口定义

--习题

-(xa3)红黑树:插入

--08XA3-1 以曲为直

--08XA3-2 双红缺陷

--08XA3-3 算法框架

--08XA3-4 RR-1

--08XA3-5 RR-2

--08XA3-6 归纳回味

--习题

-(xa4)红黑树:删除

--08XA4-1 以曲为直

--08XA4-2 算法框架

--08XA4-3 双黑缺陷

--08XA4-4 BB-1

--08XA4-5 反观回味

--08XA4-6 BB-2R

--08XA4-7 BB-2B

--08XA4-8 BB-3

--08xa4-9: 归纳体味

-本章测验

--习题

第九章 词典

-(b)散列:原理

--09B-1 从服务到电话

--09B-2 循值访问

--09B-3 数组

--09B-4 原理

--09B-5 散列

--09B-6 冲突

--习题

-(c)散列:散列函数

--09C-1 冲突难免

--09C-2 何谓优劣

--09C-3 整除留余

--09C-4 以蝉为师

--09C-5 M+A+D

--09C-6 平方取中

--09C-7 折叠汇总

--09C-8 伪随机数

--09C-9 多项式

--09C-A Vorldmort

--09C-B DSA@THU

--习题

-(d1)散列:排解冲突(1)

--09D1-1 一山二虎

--09D1-2 泾渭分明

--09D1-3 开放定址

--09D1-4 线性试探

--09D1-5 懒惰删除

--习题

-(d2)散列:排解冲突(2)

--09D2-1 平方试探

--09D2-2 一利一弊

--09D2-3 至多半载

--09D2-4 M + Lemda

--09D2-5 双蜓点水

--09D2-6 4k + 3

--09D2-7 双平方定理

--09D2-8 泾渭分明

--习题

-(e)桶/计数排序

--09E-1 大数据 + 小范围

--09E-2 桶排序

--09E-3 计数排序

--习题

-本章测验

--本章测试

第十章 优先级队列

-(a1)需求与动机

--10a1-1: 应用需求

--10a1-2: 计算模式

--10a1-3: 功能接口

--习题

-(a2)基本实现

--10a2-1: 向量

--10a2-2: 有序向量

--10a2-3: BBST

--习题

-(b1)完全二叉堆:结构

--10b1-1: 完全二叉树

--10b1-2: 结构性

--10b1-3: 形具神备

--10b1-4: 堆序性

--习题

-(b2)完全二叉堆:插入与上滤

--10b2-1: 上滤

--10b2-2: 实例

--10b2-3: 实现

--10b2-4: 效率

--习题

-(b3)完全二叉堆:删除与下滤

--10b3-1: 算法

--10b3-2: 实例

--10b3-3: 实现

--10b3-4: 效率

--习题

-(b4)完全二叉堆:批量建堆

--10b4-1 : 自上而下的上滤:算法

--10b4-2: 自上而下的上滤:效率

--10b4-3: 自下而上的下滤:算法

--10b4-4 : 自下而上的下滤:实例

--10B4-5: 自下而上的下滤:效率

--习题

-(c)堆排序

--10c-1: 算法

--10c-2: 就地

--10c-3: 实现

--10c-4: 实例

--习题

-(xa1)左式堆:结构

--10xa-1: 第一印象

--10xa1-2: 堆之合并

--10xa1-3: 奇中求正

--10xa1-4: NPL

--10xa1-5: 左倾性

--10xa1-6: 左展右敛

--习题

-(xa2)左式堆:合并

--10xa2-1: LeftHeap模板类

--10xa2-2: 算法

--10xa2-3: 实现

--10xa2-4: 实例

--习题

-(xa3)左式堆:插入与删除

--10xa3-1: 插入即是合并

--10xa3-2: 删除亦是合并

-本章测验

--本章测试

第十一章 串(上)

-(a)ADT

--11a-1: 定义+特点

--11a-2: 术语

--11a-3: ADT

--习题

-(b1)串匹配

--11b1-1: 问题与需求

--11b1-2 算法测评

--习题

-(b2)蛮力匹配

--11b2-1: 构思

--11b2-2: 版本一

--11b2-3: 版本二

--11b2-4: 性能

--习题

-(c1)KMP算法:从记忆力到预知力

--11c1-1: 重复匹配的前缀

--11c1-2: 不变性

--11c1-3 : 记忆力

--11c1-4: 预知力

--习题

-(c2)KMP算法:查询表

--11c2-1: 制表备查

--11c2-2: 主算法

--11c2-3: 实例

--习题

-(c3)KMP算法:理解next[]表

--11c3-1: 快速移动

--11c3-2: 避免回溯

--11C3-3: 通配哨兵

--习题

-(c4)KMP算法:构造next[]表

--11c4-1: 递推

--11c4-2: 算法

--11c4-3: 实现

--习题

-(c5)KMP算法:分摊分析

--11c5-1: 失之粗糙

--11c5-2: 精准估计

--习题

-(c6)KMP算法:再改进

--11c6-1: 美中不足

--11c6-2: 以卵击石

--11c6-3: 前车之覆

--11c6-4 后车之鉴

--11c6-5 : 可视对比

第十一章 串(下)

-(d1)BM_BC算法:以终为始

--11d1-1: 不对称性

--11d1-2: 善待教训

--11d1-3: 前轻后重

--11d1-4: 以终为始

-(d2)BM_BC算法:坏字符

--11d2-1: 坏字符

--11d2-2: 特殊情况

-(d3)BM_BC算法:构造bc[]

--11d3: 画家策略

-(d4)BM_BC算法:性能分析

--11d4-1: 最好情况

--11d4-2: 最坏情况

-(e1)BM_GS算法:好后缀

--11e1-1: 兼顾经验

--11e1-2: 好后缀策略

--11e1-3: 实例体验

-(e2)BM_GS算法:构造gs表

--11e2: 构造gs表

-(e3)BM_GS算法:综合性能

--11e3-1: BM之性能

--11e3-2: 各算法纵览

-(f1)Karp-Rabin算法:串即是数

--11f1-1: 化串为数

--11f1-2: 凡物皆数

--11f1-3: 串亦是数

-(f2)Karp-Rabin算法:散列

--11f2-1: 数位溢出

--11f2-2: 散列压缩

--11f2-3: 应对冲突

--11f2-4: 指纹更新

-本章测验

--本章测试

第十二章 排序

-(a1)快速排序:算法A

--12a1-1: 分而治之

--12a1-2: 轴点

--12a1-3: 构造轴点

--12a1-4: 单调性 + 不变性

-- 12a1-5: 实例

--习题

-(a2)快速排序:性能分析

--12a2-1: 不稳定 + 就地

--12a2-2: 最好情况 + 最坏情况

--12a2-3: 平均情况

--习题

-(a4)快速排序:变种

--12a4-1: 不变性

--12a4-2: 单调性

--12a4-3: 实现

--12a4-4: 实例

--12a4-5: 时间 + 空间 + 稳定性

-(b1)选取:众数

--12b1-1: 选取 + 中位数

--12b1-2: 从中位数到众数

--12b1-3: 从频繁数到众数

--12b1-4: 减而治之

--12b1-5: 算法实现

-(b3)选取:通用算法

--12b3-1: 尝试

--12b3-2: quickSelect

--12b3-3: linearSelect:算法

--12b3-4: linearSelect:性能分析A

--12b3-5 : linearSelect:性能分析B

--12b3-6 : linearSelect:性能分析C

--习题

-(c1) 希尔排序:Shell序列

--12c1-1: 策略

--12c1-2: 实例

--12c1-3: 循秩访问

--12c1-4: 插入排序

--12c1-5: Shell序列

--习题

-(c2)希尔排序:逆序对

--12c2-1: 邮资问题

--12c2-2: 定理K

--12c2-3: 逆序对

-本章测验

--本章测试

12c1-2: 实例笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。