当前课程知识点:Data Structures and Algorithm Design Part II >  12.Sorting >  C1.Shellsort.Shell's sequence >  12C1-1

返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表

12C1-1在线视频

下一节:12C1-2

返回《Data Structures and Algorithm Design Part II》慕课在线视频列表

12C1-1课程教案、知识点、字幕

同学们好。

在本章的最后一节也是这门课程的最后一节

我们来学习一种非常别致的排序算法

也就是希尔排序

希尔排序算法既有着悠久的历史

同时也仍然不失活力

该算法的别致之处在于

它不再是将输入

视作为一个一维的序列

而是将其视作为一个二维的矩阵

并且试图对矩阵的每一列

分别进行排序

如果矩阵当前的宽度为w

那么我们就将所有这w列

各自的排序总称为w-sorting

实际上每一次Shellsort排序的过程

都是由若干个宽度不同的

W-sorting构成的

如果矩阵的每一列都已经过排序

我们就称之为w-ordered

实际上矩阵最开始比较宽

w比较大

此后Shellsort会逐步的压缩矩阵

使之越来越高越来越窄

每压缩一次都随机执行一趟

对应的w-sorting

从而使之变成W-ordered

我们也可以通过这样的一组图

来说明这一过程

比如这可能就是最初的那个矩阵

相应的比较宽比较矮

那么在执行完对应的Wk-sorting之后

Shellsort会对这个矩阵进行重组

使之成为一个相对更窄

但同时更高的矩阵

接下来对应于新的这个宽度

WK减1也会做一趟逐列的排序

而在此之后

Shellsort又会对它进行重组

使之变成这样一个更加的窄

更加高的矩阵

这个过程将持续的进行下去

总之矩阵会变得越来越高越来越窄

直到最终变成只有一列

同样的对最后这个矩阵

我们也需要来做一次对应的

W-sorting

只不过此时的W等于1

所以我们也称之为one-sorting

可以看到整个Shellsort的过程

使用了一系列的宽度

也就是WK Wk减1

以及一直到W3 W2和W1

这些宽度和在一起

构成了所谓的步长序列

step sequence

当然这些矩阵宽度被使用的次序

恰好与它们在序列中的次序相反

然而无论如何

它们都必须是逐个单调递减的

没错在算法的执行过程中

我们所采用的矩阵宽度

会逐步的递减

所以希尔排序算法

也称作为递减增量法

请注意我们这里的步长序列h

实际上除了我们刚才所说的单调性

以及它的首项必须为一

我们对它暂时还没有更多的要求

是的

这种序列有很多种可能的选择

采用不同的步长序列

Shellsort的性能也会有所不同

实际上Shellsort只是一个框架

你采用什么样的步长序列

就会得到什么样的算法

从这个意义上讲Shellsort

就像一个播放机

你往里头放入什么样的CD

它就会播放什么样的音乐

因此我们宁愿说Shellsort是一个算法

不如说它是一类算法

我们注意到既然任何步长序列

都要求首项W1等于1

所以任何Shellsort

都是以one-sorting结束的

而任何一次这样的one-sorting

其实也就相当于全局的排序

因此最终的输出结果

也必然是正确的排序序列

因此这个算法的正确性

是毫无疑问的

当然至此你可能会有一个疑问

既然无论如何

最终都要做一次one-sorting

那么此前的这些排序又有什么意义呢

是的

这正是Shellsort的奥妙所在

不过现在回答这个问题

还为时尚早

接下来我们不妨通过一个具体的实例

首先来切实的感受一下

希尔排序的执行过程

Data Structures and Algorithm Design Part II课程列表:

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除:双旋

--07D3-3 删除:实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

12C1-1笔记与讨论

也许你还感兴趣的课程:

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