当前课程知识点：数据结构 > 第8章 排序 > 8.4 选择排序 > 讲解（上）
本节，我们来学习选择排序
选择排序
它基于的思想是，每一趟选出当前序列的最小者或者最大者
然后，把它放到合适的位置
第一种选择排序
叫简单选择排序
第一趟，选出n个元素当中的最小者，放到位置1
比如，我们这里给出5个元素
第一次，在这5个元素当中，选出最小的这个1
我们这里橙色背景的，表示当前的最小值，1作为5个元素当中的最小者
排成正序
它肯定要放到1位置
下一趟
我们应该选出后4个元素当中的最小值
最后一趟
我们只用选出后2个元素
当中的最小值，就可以了
最小值3
它放到n-1位置
所以，简单选择排序
它一定会执行n-1趟
因为，你每次都选出当前的最小值，放在合适的位置
你一定要执行n-1趟，才能选出
n-1个最小值，放到合适的位置
最后一个元素
直接放到最后一个位置，就可以了
现在，我们来看看它的算法实现
我们对L进行简单选择排序
因为，我们要交换元素
所以，要用一个临时的变量
i从1开始，一直到n-1
也验证了我们刚开始说的，简单选择排序
一定会执行n-1趟
每一趟
我们应该找出当前的较小者，怎么找呢
我们声明一个变量min
它代表r[i]到r[n]中的最小者的下标
注意，它代表的是下标
而不是最小者的值
因为
第一趟，我们就认为第1个值是(当前)最小的
第二趟，我们就认为第2个值是(当前)最小的
从i+1这个元素开始比较
因为一开始，在内层循环之前
我已经将i赋值给min了
后面比较大小的时候
我只需要从i那个元素后面的那个元素，也就是下标为i+1的那个元素
开始，一直到最后的元素
小于等于n，去找最小者
如果当前的最小者(注意min是作为下标来用的)
它是大于等于j指向的那个元素的
那么，就将min修改成当前的较小者的下标
我们是将j赋值给min
而不是r[j].key赋值给min
因为，min是下标(再强调一下)，这个内层循环结束之后
min就指向
第i到第n个元素当中
最小者的下标
那我们只需要去交换
第i个位置和min指向的那个位置的元素，就行了
为什么要交换呢
因为，你直接将min指向的那个元素，放到i的位置
会把i那个位置的元素覆盖掉
所以，我们交换一下
如果min和i是相等的
自己和自己交换，就没有意义了
所以，我们加了一个if判断，min和i不相等的时候
我们才去交换
这就是简单选择排序它的算法
我们来分析一下它的时间复杂度
因为，外层的循环总会执行n-1次，而内层的循环
它是从i+1，一直到n的
不管怎么样
它(内层循环)也是关于n和i的一个函数
一个线性函数
最终
总的循环次数，肯定是关于n的一个等差数列
最终就是n^2
无论最好还是最坏
它跟给定的n个元素
它们的初始状态，是没有关系的
空间复杂度
因为用到了一个临时变量
那就是O(1)，这个算法
它也是不稳定的
因为，我们在交换min和i指向的元素过程当中
min和i有可能相差比较大
那也会出现可能跳过相同关键字的这种情况
所以，简单选择排序
它也是不稳定的
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
