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

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

12C1-5在线视频

下一节:12C2-1

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

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

我们在这里结识的第一个步长序列

就出自于希尔排序的发明者

Shell本人之手

我们接下来就会看到

这个序列存在很多缺点

尽管从某种意义上来看

它非常优美

因为我们注意到

它的每一项都整齐划一的是

2的k次方的形式

也就是说每一项都是前一项的两倍

那么这个序列的缺点

就集中体现在它在最坏情况下

可能会导致n平方量级的运行时间

为此我们可以构造这样一个

具体的实例

我们首先来考察

两个整数区间

也就是0到2的n减1次方

以及2的n减1次方

到2的n次方

其中包含的整数都是2的N减1次方个

只不过在数值上前者更小

而后者更大

接下来我们将这两组整数

分别的打乱次序

并相应的构成两个字序列A以及B

然后我们按照ABAB交错的形式

将它们会合为一个完整的序列

比如对于n等于4而言

这就是一个可能的生成序列

可以看到它是有两个

规模都为八的子序列交错构成的

子序列A中的元素

都被安置在秩为奇数的位置

而对称的子序列B中的元素

都被安放在秩为偶数的位置

现在我们假设就采用希尔的序列

来对它进行排序

我们考察算法的倒数第二步

也就是以二为间隔的

那轮排序刚刚结束的时候

我们可以断言

此时序列的组成必然是这样

也就是说原先来自于子序列A中的

那些元素

依然占据着秩为奇数的位置

而且这八个元素的相对次序

已经是完全有序的

同时对称的原先来自于子序列

B中的那些元素

也必然仍就占据着

秩为偶数的那些位置

而且仅就这八个元素而言

它们之间的相对次序也已经是有序的

这两个字序列在这个时刻的有序性

并不难理解

在刚刚过去的这一论排序中

这两个子序列

恰好各自就是独立成为一列

因此所谓的2-sorting

其实就是对这两列分别进行排序

所以它们的结果自然应该是

各自有序的

当然刚才我们所指出的另一个现象

更会引发我们的好奇

也就是说无论我们此前

经历过多少趟的排序交换

来自于子序列A和子序列B中的元素

始终都是分别占据着

秩为奇数和偶数的位置

二者泾渭分明没有任何的元素互换

为此我们需要反观希尔序列

我们注意到在这个序列中

除了第一项其余各项都是偶数

没错 偶数

这就意味着在这些项

所对应的每一个重组的

二维矩阵中同属一列的元素

或者都来自于集合A

或者都来自于B

自然不会发生A与B之间的元素互换了

因此直到执行完2-sorting之后

这两个序列必然都是井水不犯河水

互补相扰

然而这恰恰正是问题所在

对于这样的序列

在接下来的最后一趟排序

也就是one-sorting中

我们必然需要付出高昂的代价

因为在这个序列中

依然包含着大量的逆序对

我们不妨只统计B中的元素

所参与构成的逆序对

首先是全局最大的15

它与其后的七

就构成了一个逆序对

接下来再考察4大的14

不难看出

它与6和7构成了两个逆序对

再接下来是13

它与5 6 7 总共构成了

三个逆序对

以下类推元素12

将与4 5 6 7总共构成四个逆序对

我想你已经看出其中的规律了

没错

B中的各元素所参与构成的逆序对数

恰好构成一个算术级数

没错算术级数

我想经过这门课的学习

你现在应该有了一个直觉的反馈

是的

这样一个算术级数对应的将是

平方量级的运行成本

也就是说算法的效率

已经退化为个与起泡排序相当了

当然在这里我们并不满足于

仅仅指出希尔排序的缺点

而更重要的是

我们需要探究导致这种缺陷的根源

让我们将目光再次投回到希尔序列

我们会发现与其说

其中大量的元素都是偶数

不如更一般的说

其中的各项并非互素

因此每一轮的排序

都有大量的精力浪费于

对前一抡排序工作的重复之上

是的

相邻项要尽可能的互素

这样我们也就拿到了

打开新方法大门的钥匙

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-5笔记与讨论

也许你还感兴趣的课程:

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