当前课程知识点:Data Structures and Algorithm Design Part II > 12.Sorting > C2.Shellsort.Inversion > 12C2-3
返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part II》慕课在线视频列表
现在还是回到我们的线性组合
考察我们的待排序序列
如果它既是g-ordered
同时也是h-ordered
这样的序列也称作是
g h-ordered
实际上这样的序列也必然会以
G和H之和为步长是有序的
我们可以通过这个图
来简明的证明这一点
在整个序列中考察任何一对
相距g加上h的元素
我们说它们必然是顺序
因为我们可以找到
居于它们中间的
这样一个特定的元素
这个元素到前一元素的距离为g
而到后一元素的距离为h
于是以这个中间元素为桥梁
根据不等式的单项传递性
我们自然就可以得知
这一对间隔为g加h的元素
也必然是顺序的
实际上这个结论也可以进一得推广到
g和h的任何一个线性组合
我们仍然通过这组图来加以说明
在这个序列中
我们考察任何一对间距为
这个线性组合的元素
为了证明这一对元素之间的顺序性
我们无非是将刚才的方法推而广之
也就是说
我们需要引入更多的中间桥梁
比如这里给出的就是一种具体的方案
我们首先以g为间隔
连续的取出m个元素
在这些间隔位置上的所有元素
必然是单调非降的
接下来我们在以h为间隔
连续的取出n个元素
同样的这n个元素
也必然是单调非降的
于是通过所有这些单项不等号的串接
我们也就自然的证明了
这样一对元素之间的顺序性
由以上我们可以概括出一个结论
也就是凡是间距
可以表示为线性组合的
任何一对元素必然是顺序的
简而言之凡能表示为线性组合
则必然顺序
现在我们将注意力集中于序列中
秩为i的那个元素
如果g和h是互素的
而且整个序列已经是
同时关于g和h有序的
那么相对于这个元素
哪些元素必然是顺序的
反过来哪些元素才有可能是逆序的
我们说实际上可能逆序的元素不会很多
确切的讲无非就是刚才
关于g和h的那个x的
也就是不能由g和h线性组合
生成的那个最大的整数
你能看出其中的原因吗
没错
对于这个区间之后的
任何一个元素而言
它与i的距离已经超出了
那个最大的预值x
所以它们之间的间隔
也必然可以表示为g和h的线性组合
而我们刚刚总结过
凡是能够表示为线性组合的
也就是顺序
反过来这也就意味着
i这个元素所能参与构成的逆序对
只可能出现与这样一个范围
而随着希尔排序的不断迭代
这个范围也会不断的缩小
没错
逆序列的总数会不断持续的减少
因此你能想到点什么吗
没错
插入 排序
我们知道
插入排序具有输入敏感性
它的实际运行时间将线性正比于
序列中所含逆序对的总数
至此我们终于弄明白了
为什么在希尔排序的底层
我们更加倾向于使用
插入排序算法
实际上按照以上的优化思路
后人针对希尔排序
曾经涉及过许多更为优化的步长序列
比如PS序列
Pratt序列
以及Sedgewick序列
关于这些序列的详细介绍
及其性能分析
详见我们的教材以及习题解析
-A.introduction
--07A-1
--07A-2
--07A-3
--07A-4
--07A-5
-A.introduction--Homework
-B1.BST : search
--07B1-1
-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
-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
-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
-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
-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
-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
-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
-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
-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