当前课程知识点：数据结构（Data Structures） > 7. Sorting > 7.3 Selection Sort > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
下面我们来学习另外一种简单的排序算法
选择排序算法
这里我们通过一个形象的硬币排序的例子
来去说明选择排序它的原理
在这个桌面上有一组硬币
现在我们的问题是
请大家把这组硬币
按照它们的尺寸从小到大进行排序
我们通常的做法是
首先从所有的硬币中挑选出最小的硬币
然后把这个硬币摆在最前面的位置
接下来我们再从剩下的硬币里面
挑选出最小的硬币
然后再将这个硬币摆在第二个位置上面
这个过程反复地执行
我们每次都是从剩余的硬币中
挑选出最小的硬币
并且把它摆在合适的位置上面
我们继续不断地选择
一个个地选择出来
直到最后面
所有的硬币排成了一个有序的序列
这个就是选择排序的过程
非常简单而且直观
就是不断地从剩下的元素里面
挑选出最小的
然后把它放置到一个合适的位置上面去
下面我们把这个硬币的例子
替换成为一个整数序列的例子
来进一步说明排序说明它的原理
我们对这一组整数进行选择排序
首先我们从所有的整数里面
挑选出最小的整数13
因为它是最小的
所以应该把它排在数列的最前面
所以我们把13和0号位置的元素
进行了交换
接下来我们继续从剩下的元素里面
挑选出最小的整数14
因为14是除了13之外最小的元素
所以我们把14和第1号位置的元素
进行交换
后面的过程是类似的
我们继续选择最小的元素15
然后交换到2号位置
继续选择最小的17交换到3号位置
然后选择出最小的20交换到4号位置
选出23交换到5号位置
选出28交换到6号位置
最后剩下的42就是整个序列里面
最大的整数
对于有n个元素的序列来说
选择排序它需要进行n-1次的选择
以及交换的过程
我们采用一个迭代变量i
来去标记每次选择的过程
那么在第i次选择的时候
我们主要做的事情就是
从数组剩下的元素里面
也就是从i号位置一直到n-1号位置
这些元素里面挑选出最小的那个
然后把它交换到数组中第i号位置上面去
例如在这里面第0次迭代的时候
我们就是要把从0号到n-1号
这些所有位置的元素里面挑选出最小的13
然后把它交换到0号位置
而第一次迭代的时候
就是从1号位置到n-1号位置
所有的元素里面
挑选出最小的14
然后把它交换到1号位置上面去
我们下面来实现这个选择排序的过程
这里定义了Selection Sort函数
这个函数有两个参数
第一个是存放数据的数组 Array
第二个是数组中的元素个数n
整个排序的过程
我们需要n-1次的选择的过程
所以这里我们采用了一个for循环
这个循环语句它执行了n-1次
在每次循环的过程中
我们需要从数组中的i号位置
一直到n-1号位置的所有位置里面
挑选出一个最小的元素
所以这里面我们定义一个变量min
用来去记录这个最小的元素它所在的位置
初始化的时候
我们把min设置为i
为了找到从i号位置到n-1号位置中的
最小元素
我们将这个区间的所有元素
一一进行比较
所以我们这里面采用了另外一个for循环
我们让变量j取遍从i+1到n-1的所有位置
我们将j位置的元素和min位置的元素
进行对比
如果比它小我们就将min更新为j
所以这个min变量
它始终记录的是比较小的元素
它所在的位置
当这个for循环执行完毕的时候
min它所记录就是从i号位置到n-1号位置中
最小的元素
然后我们再将这个最小的元素
交换到i号位置上面去
所以我们这里面将min号位置的元素
和i号位置的元素进行了一个交换
当这个选择的过程执行了n-1次之后
我们最后就会得到一个
从小到达排序的结果
下面我们来分析一下
选择排序算法它的复杂度
算法是由两重for循环来实现的
这个循环执行的次数和序列中数据的分布
是没有关系的
而只是和数据的个数n是有关系的
所以我们可以推导出
这段代码它的复杂度在最好的情况下
最差的情况下以及平均的情况下
都是θ(n2)
最后我们来分析一下
选择排序它的稳定性
我们通过一个非常简单的例子来说明
选择排序它是一个不稳定的排序
在这个例子里面有三个整数
其中有两个是等于20的
我们用不同的颜色来进行区分
排序需要经过两次选择交换的过程
其中第0次选择的时候
我们首先选择出最小的元素 它是17
然后我们把17和0号位置的黑色20
进行交换
经过这次交换之后
黑色的20跑到了红色20的后面
第一次选择的时候
我们将从1号位置到2号位置中
选择出最小的元素
根据我们选择排序的代码
我们选择的是红色的20
然后因为这个20本身就处在于1号位置
所以保持它的位置不变
因此它最终的排序结果是黑色的20
在红色20的后面
这两个20的位置经过排序之后
它们先后次序发生了变化
而这个相对位置的变化
是由于跨越若干位置的数据交换
它所造成的
所以我们说选择排序
它是一个不稳定的排序算法
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
