当前课程知识点:Data Structures and Algorithm Design Part II > 12.Sorting > C2.Shellsort.Inversion > 12C2-2
返回《Data Structures and Algorithm Design Part II》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part II》慕课在线视频列表
回到排序问题
我们首先来引入h-sorting
以及h-ordered的这两个概念
在某个序列中
如果任何一对距离为H的元素
都保持前小后大的次序
我们就称它为h-ordered
也就是以H为间隔是有序的
当然作为其中的一个特例
在任何一个one ordered的序列中
根据定义任何一对相邻的元素
彼此之间都是顺序的
你应该记得我们在最初介绍
起泡排序算法时就指出
某个序列中只要任何相邻的元素之间
都是彼此顺序的
那么必然就是整体有序的
所以我们说任何one-ordered的序列
也必然是全局有序的
也就是我们排序算法
最初需要输出的结果
那么对于任何一个随机序列
如何使它变成是H-ordered的呢
实际上如这幅图所示
我们只需采用希尔排序的那种方法
将输入的(一维)序列
在逻辑上转换为一个
宽度为H的矩阵
然后分别的逐列排序
你应该记得将整个序列
在逻辑上转化为一个
宽度为H的矩阵
并且逐列进行排序
在希尔排序中就称为h-sorting
由此我们可做一简洁的归纳
也就是任何一个序列
在做过h-sorting之后
必然是h-ordered
你应该记得在希尔排序中
每向前迭代一步
对应的矩阵宽度都会相应的减少
比如从前一轮的g减少为后一轮的h
我们知道在经过前一轮的逐列排序之后
整个序列应该是g-ordered
而在后一轮的逐列排序之后
这个序列也自然的应该是h-ordered
那么在整个序列达到
以h为间隔有序的同时
此前以g为间隔的有序性
是否能够依然得以延续呢
这个问题的答案
并不是那么一目了然
所幸的是Knuth
已经在他那本著名的专著中
给出了正面的答案
Knuth指出任何一个原先
已是g-ordered的序列
在此后经过h-sorting之后
依然保持是g-ordered
也就是说相对于任何一个
固定间隔而言的有序性
在希尔排序的过程中
将会不断的保持
并且持续的积累下来
这个定理的证明
需要颇费一些时间
如果你对此感兴趣
不妨在课后去参考我们的习题解析
-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