当前课程知识点:Data Structures and Algorithm Design Part II >  12.Sorting >  A4.Quicksort.Variation >  12A4-4

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

12A4-4在线视频

下一节:12A4-5

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

12A4-4课程教案、知识点、字幕

在告别本节之前

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

来切实的体验

快速排序的这个新的版本

这里的输入序列由11个元素构成

这个算法会首先将首元素6

作为侯选轴点

而其余的元素则整体构成子序列U

当然相应的子序列L和G此时都是空

以下进入算法的迭代部分

首先在第一步迭代中

我们考虑的是U 当前的首元素3

这个元素要比侯选轴点更小

因此它应该被归入到子序列L中

在我们刚才实现的算法中

这就对应于if的分支

当然这是一种退化的情况

因为这个兑换

实际上就是它自己和自己

所以在位置上这个元素

并没有实质的改变

然而此后在逻辑上

子序列L将拥有第一个元素

而不再是空

接下来我们继续考察新的首元素8a

因为它在数值上要大于侯选轴点

所以对应于los那个分支

这是一个只需简明处理的分支

具体来说

我们在这种情况下

只需简明的利用k++

从而在使得子序列U

缩短一个单位的同时

使得子序列G拥有了第一个元素

再接下来我们会进而考虑

新的首元素1

可以看到它比侯选轴点要更小

因此应该被归入到子序列L当中

我们需要令它和子序列G的首元素

互换位置

当然此时G的首元素

也就是它那个唯一的元素8a

可以看到在经过了这样一次交换之后

二者的位置的确颠倒了过来

请注意在经过了这样一次交换之后

更主要的在逻辑上是等效于子序列L

向后拓展了一个单位

同时子序列G滚动式的后移了一个单位

接下来我们继续考察

子序列U的首元素也就是5a

可以看到

它依然应该被归入到子序列L当中

为此我们依然需要令它

和子序列G的首元素

也就是8a做一次交换

经过了这样的一次交换之后

不仅这两个元素的相对位置

颠倒过来了

而且更重要的是在逻辑上

子序列L又继续向后拓展了一个单位

同时子序列G也滚动式的

又后移了一个单位

接下来我们依然要考察子序列U

新的这个首元素9

作为大于侯选轴点的元素

它自然应该归入子序列G中

我们知道这对于算法中的los分支

因此只需简明的利用k++

就可以在逻辑上利用子序列G

向后拓展一个单位

在以下我们仍然是要

考察子序列U的首元素

这回轮到的是8b

因为它不小于侯选轴点

因此同样对应的是los那个分支

也就是说

我们依然只需简明的利用K++

就可以使得子序列G

继续向后拓展一个单位

接下来的这个首元素4

要小于侯选轴点

所以它对应的是if分支

于是我们需要令它

与子序列G的首元素8a互换位置

在经过了这样一次交换之后

子序列L向后继续拓展了一个单位

同时子序列G也滚动式的

后移了一个单位

再接下来的这个首元素5b

同样应该被归入于子序列L当中

因此我们仍然需要令它

与子序列G的首元素9互换位置

同理在经过了这样一次交换之后

子序列L得以向后继续拓展一个单位

同时子序列G再次滚动式的后移一个单位

现在轮到新的首元素7了

它要比侯选轴点更大

所以应该通过简明的K++

将它归入到子序列G中

同时子序列L保持不变

现在轮到子序列U的最后一个元素2了

它比侯选轴点更小

因此应该被归入到子序列L中

我们的处理手法依然

也就是要利用这个元素

与子序列G当前的首元素8b

做一次交换

在经过最后的这一次交换之后

L再次向后拓展了一个单位

而子序列G

再次滚动的后移一个单位

至此子序列U变成空

因此循环得以退出

在算法终止之前

我们还需要完成最后一步

也就是利用侯选轴点就位

并成为一个名副其实的轴点

你应该记得我们的做法是

令这个侯选轴点

与当前子序列L的末元素

也就是2互换位置

可以看到在如此交换之后

候选节点6的确成为了一个

名副其实的轴点

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

12A4-4笔记与讨论

也许你还感兴趣的课程:

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