当前课程知识点:Data Structures and Algorithm Design Part I >  03.List >  D.Selectionsort >  03D-1

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

03D-1在线视频

下一节:03D-2

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

03D-1课程教案、知识点、字幕

欢迎同学们回来

与向量那一章的做法一样

列表这一章 接下来几节

也将针对列表这种结构的特点

介绍几种典型的排序算法

比如 这一节我们要介绍的就是

选择排序

这种排序算法其实并不神秘

我敢打赌 你在日常生活中

此前肯定已经甚至经常使用这种方法

举个例子

假设你有一篮子苹果 或大或小

如果你需要从小到大

把它们排成一个序列

那你会怎么做呢?

我想大家常用的一种方法

应该是这样的

首先在其中挑选出最大的

接下来 在剩下的中 挑选出最大的

也就是整个来说 次大的

再往后呢 当然是接下来的最大的

也就是整个的第三大的

不难看出 这个过程可以继续下去

直到篮子中只剩下最后那只苹果

虽然我们这里画得很夸张

但是它确实是全局最小的那个

可以看出 在这个过程中

我们所采用的策略

或者说原则非常的简单

具体来讲 就是

每一次我们只需在篮子中

找出当前最大的那只苹果

并且随即将它转移到桌子上

这个策略是如此简明

以致于我们可以反复地进行

直到最后

可见 这里每一步所做的

实质的关键动作

其实无非就是所谓的选择select

而基于这样一种选择过程

和策略的排序算法

就叫作selection sort

即便是在这门课中

我们也不是第一次接触到选择排序

我并没有骗你

回顾一下此前

我们所介绍过的bubble sort

其实它也是一个不折不扣的

selection sort

难道不是吗?

我们来看一下

在这样一个算法的过程中

我们曾经讲过

它的不变性可以表述为

整个序列总是可以

分成前后两个部分

其中后面的一个部分

是由一系列已经就位的元素组成的

它们构成了一个有序的sorted的部分

而前半部分的元素呢

数值的分布是随机的 或大或小

但是就数值而言

它们都绝对不会超过这样一条黄线

也就是说 如果从分布讲

它们都应该落在

这样一个黄色的矩形中

那这个算法我们讲过

是由一趟又一趟的扫描交换构成的

在接下来的一趟扫描交换中

最实质的故事实际上是

从当前最大的那个元素开始的

我们讲过此后的情节是确定的

也就是说 这个最大的元素

必然会和随后的邻居

以及再随后的邻居

以及再随后的邻居

不断地交换

直到它最终

被移送到

这个黄色区域的末尾

于是这个有序的S部分

就可以向左侧拓展

或者说生长一个单位

这也是我们所说的

这个算法的单调性

纵观这个过程

并且与上面的选择排序做一对比

我们会发现 二者之间惊人的相似

也就是每一次扫描交换的作用

其实实质上都等价于

找到这个最大节点

并且随即将它转移至有序

和无序子序列的分界点

从这个角度来看

起泡排序确实就是

一个不折不扣的选择排序

那反过来 既然如此

还有什么必要去专门讨论选择排序呢?

原因在于 起泡排序的效率太低

正如我们此前说过的 在最坏情况下

它需要n平方

我们注意到 这个效率

是完全可以改进的

细加观察我们可以发现

在起泡排序的过程中

所执行的计算无非两类

一类就是相邻元素的比较

另一类才是元素位置的交换

然而很遗憾

在这里将最大元素

转移至合适的位置这样一个任务

是由一系列的短距离

实际上是相邻元素之间的移动构成的

这种小步慢跑式的移动

正是低效率的来源

所以反过来

既然我们最终实际上无非

就是要将这个最大的元素

挪到最终的位置

为何不直接一次性地

来完成这项工作呢?

没错

这正是我们改进的思路

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

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

03D-1笔记与讨论

也许你还感兴趣的课程:

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