资源简介

(共27张PPT)
第2课 排序算法
目录
01
问题背景与挑战
02
选择排序基本原理
03
算法步骤拆解
04
编程实现与优化
05
应用场景与扩展思考
问题背景与挑战
PART ONE
智力运动会排序任务
目标是通过合理的方法，利用天平完成10个苹果的质量排序，重点在于找到高效的排序方式，以最短时间达成排序要求。
任务目标
此任务看似简单，但要高效完成并非易事，这就引出了对算法设计的需求，需要借助合适的算法来减少比较次数，提高排序效率。
引出算法需求
小睿的学校举行智力运动会，其中一项挑战是对10个大小相似但质量不同的苹果排序。参赛者借助天平，要将它们按质量由小到大排列，用时最少且方法最佳者获胜。
任务背景
01、
02、
03、
排序的本质与核心问题
排序的本质
排序的本质是一个不断比较每两个苹果质量的过程。在这个过程中，通过比较确定元素之间的大小关系，进而对元素的位置进行调整。
01
02
元素比较
在对苹果排序时，需要将每个苹果与其他苹果进行比较，判断其质量大小，这是确定苹果最终顺序的基础操作。
03
位置交换
当比较出两个苹果质量的大小关系后，如果顺序不符合要求，就需要交换它们的位置，以此逐步构建出有序序列。
手动排序的局限性
在对10个苹果进行手动排序时，随着苹果数量的增加，比较和交换的次数会急剧上升。例如，每增加一个苹果，比较次数就会大幅增加，导致排序效率低下。
效率瓶颈体现
01
若苹果数量从10个扩展到100个甚至更多，人工操作的难度和时间成本将难以承受。人工排序不仅容易出错，而且效率极低，无法满足大规模数据的排序需求。
规模扩展挑战
02
面对大规模数据的排序任务，手动排序的局限性凸显，这就迫切需要自动化的排序算法来提高效率和准确性，以应对不断增长的数据规模挑战。
对自动化的需求
03
选择排序基本原理
PART TWO
算法核心思想
每一轮排序都是在前一轮的基础上进行，不断缩小未排序数据的范围。随着轮次的推进，已排序序列逐渐增长，未排序序列逐渐缩短，最终实现整个序列的有序排列。例如在对10个苹果排序时，第一轮找出最轻的苹果放在首位，第二轮在剩余9个苹果中找出第二轻的放在第二位，依此类推。
递进式排序逻辑
选择排序采用分层构建的方式来生成有序序列。从序列的起始位置开始，逐步将未排序数据中的最小元素挑选出来，放置到已排序序列的末尾，一层一层地构建出完整的有序序列。
分层构建有序序列
双循环结构解析
选择排序中的外层循环用于控制排序的轮次。以对n个元素进行排序为例，外层循环会执行n - 1次。每一轮循环都对应着确定一个位置的元素，使其成为有序序列的一部分。比如对10个苹果排序，外层循环就会执行9次，依次确定从最轻到第九轻的苹果位置。
外层循环控制轮次
1
内层循环的主要作用是在每一轮中查找未排序数据中的最小元素。在内层循环中，会将当前轮次起始位置的元素与未排序部分的其他元素逐个进行比较。如果发现有比当前元素更小的元素，就记录下该元素的位置，循环结束后，就能确定这一轮中的最小元素。
内层循环执行极值查找
2
算法特征总结
选择排序是一种原地排序算法，这意味着在排序过程中，除了输入的数组本身，不需要额外的大量存储空间来完成排序操作。它只需要几个额外的变量来辅助记录数据的位置和进行比较交换等操作，在空间复杂度上具有一定优势。
选择排序是不稳定的排序算法。在排序过程中，相等元素的相对顺序可能会被改变。例如，假设有序列 [5a, 3, 5b]，在选择排序时，可能会将5a与3交换位置，导致原本在5a后面的5b跑到了5a前面，改变了相等元素5a和5b的相对顺序。
原地排序特征
不稳定性特征说明
算法步骤拆解
PART THREE
首轮极值定位
首轮要找出10个苹果中质量最轻的，在第一步比较出质量轻的苹果后，需用这个苹果分别与2 - 9号苹果进行比较。如果该苹果比其他苹果重就交换，轻则不交换，通过这n - 1（这里n = 10，即9次）次比较，就能找出质量最轻的苹果，并把它放到首位。
全面比较找最小
在选择排序中，首轮极值定位从序列头部开始。例如对10个苹果排序，首先使用天平比较0号和1号位置的苹果。若0号位置的苹果重，则交换两个苹果的位置，否则不交换。
比较的起始步骤
次优元素递进选择
在找出最轻的苹果并放置到首位后，次优元素的选择范围缩小到剩余的苹果。比如第二轮，用1号位置的苹果，重复第一轮的步骤，在剩余9个苹果中选出第二轻的苹果。
缩小范围选次优
01
每一轮都在不断缩小的未排序序列中选择当前轮次的最小元素。随着轮次推进，已排序序列逐渐增长，未排序序列逐渐缩短，通过这种递进方式完成所有元素的筛选。
递进选择的过程
02
每轮选出的次优元素，会放置到已排序序列的末尾，也就是当前轮次对应的位置。如第二轮选出的第二轻的苹果放置在1号位置。
确定位置放置元素
03
比较次数数学建模
根据等差数列求和公式 (S_n = frac{n(a_1 + a_n)}{2})（其中n为项数，(a_1)为首项，(a_n)为末项），这里项数为n - 1，首项为n - 1，末项为1。将其代入公式可得总比较次数 (S = frac{(n - 1)(n - 1 + 1)}{2} = frac{n(n - 1)}{2})。
在选择排序中，每一轮比较的次数构成一个等差数列。第一轮比较n - 1次（n为元素总数），第二轮比较n - 2次，以此类推，最后一轮比较1次。例如对10个苹果排序，第一轮比较9次，第二轮比较8次……第九轮比较1次。
求和公式推导
等差数列的形成
比较次数数学建模
以10个苹果为例，将n = 10代入公式，总比较次数为 (frac{10times(10 - 1)}{2} = 45) 次，这就是通过数学建模得出的选择排序对10个元素进行排序的总操作量。
总操作量计算示例
时间复杂度分析
选择排序的时间复杂度为O(n )，这意味着算法执行时间与数据规模n的平方成正比。当数据规模n增大时，算法执行时间会急剧增长。
O(n )的含义
01
通过绘制算法效率曲线可以直观看到，随着数据规模n的增加，O(n )曲线上升趋势明显。与其他更高效的排序算法（如O(n log n)的快速排序）相比，选择排序在处理大规模数据时效率较低。
效率曲线图示说明
02
由于时间复杂度为O(n )，选择排序适用于小数据量的排序任务。在数据量较小的情况下，其简单直观的特点使其易于实现和调试，但对于大规模数据排序则不太适用。
对算法应用的影响
03
编程实现与优化
PART FOUR
数据存储结构设计
在数据存储结构设计中，数组是常用的选择。例如在对苹果质量排序任务里，可使用数组来存储每个苹果的质量数据。数组具有连续存储的特点，能方便地通过索引访问元素，为后续的排序操作提供基础。
数组的选择
索引操作在整个排序过程中至关重要。通过索引，我们可以准确地定位数组中的元素，进而进行比较和交换等操作。比如在选择排序中，利用索引可以快速找到未排序部分的元素，并与已排序部分进行关联操作。
索引操作的意义
数据存储结构设计
实现数组与索引操作的方案需要综合考量。要根据数据量大小、操作的复杂度等因素来设计。对于小数据量的苹果质量排序，简单的一维数组和基本的索引操作就能满足需求，但对于大数据量，可能需要更复杂的结构和算法。
实现方案的考量
极值索引追踪策略
在每一轮排序中，从数组的特定位置开始遍历，将第一个元素的索引设为临时变量初始值。然后依次与后续元素比较，若遇到更小的元素，就更新临时变量为该元素的索引，以此准确记录最小元素位置。
在极值索引追踪策略里，临时变量发挥着关键作用。以选择排序找最小元素为例，通过设置临时变量，可以在遍历数组时记录当前找到的最小元素的索引位置，方便后续操作。
记录最小元素位置的过程
临时变量的作用
极值索引追踪策略
这种通过临时变量记录最小元素位置的策略，使得排序过程更加有序和高效。它避免了每次比较都进行复杂的操作，只需在遍历结束后，根据临时变量记录的索引进行相应处理，提高了排序效率。
策略的优势
交换操作优化技巧
采用这些减少冗余交换操作的实现方法，能显著提升排序算法的性能。特别是在数据量较大时，减少的冗余操作能大幅降低计算时间，提高程序运行效率。
实现方法的效果
为减少冗余交换操作，可在比较时增加判断条件。比如在确定最小元素索引后，先判断该索引是否就是当前需要交换的位置，如果是则无需交换，直接进入下一轮排序，从而节省计算资源。
减少冗余的方法
在排序过程中，需要识别冗余交换操作。例如在选择排序时，如果当前比较的元素已经是最小的，却仍然进行不必要的交换，这就是冗余操作。通过分析比较条件，可以发现这类无意义的交换。
冗余交换操作的识别
应用场景与扩展思考
PART FIVE
小数据量场景优势
对于小数据量排序需求，选择排序简单直观的特点使其易于实现和调试。像一些简单的小型系统，只需少量代码就能完成排序功能，降低开发成本。
简单易实现
在某些智能家居设备中，如传感器数据量较小且对排序要求不高时，选择排序算法可快速对数据进行排序处理，保障设备正常运行。
典型应用示例
在小数据量场景下，选择排序算法占用计算机资源较少。例如在嵌入式设备中，其硬件资源相对有限，选择排序算法不会给设备带来过多负担，能高效完成小数据量的排序任务。
资源占用少
01、
02、
03、
与其他算法的对比
时间复杂度方面，选择排序和冒泡排序平均和最坏时间复杂度均为 (O(n^2))，但选择排序交换次数更少。空间复杂度上，二者都为 (O(1))。
与冒泡排序对比
插入排序在数据基本有序时时间复杂度为 (O(n))，而选择排序始终为 (O(n^2))。空间复杂度上，插入排序同样为 (O(1))，二者在空间占用上表现相当。
与插入排序对比
选择排序在小数据量时优势明显，但面对大数据量，冒泡排序和插入排序在特定情况下可能更具效率，开发者需根据实际情况选择合适算法。
综合对比结论
排序稳定性改进
在一些特定应用场景中，排序稳定性至关重要。例如在成绩排名系统中，相同成绩的学生顺序应保持不变，稳定排序算法能满足此类需求。
稳定性的重要性
01
为改进选择排序的稳定性，可通过记录每个元素的原始位置。在排序过程中，当遇到相等元素时，按照原始位置顺序处理，从而实现稳定排序。
记录原始位置实现稳定版本
02
改进后的稳定版本选择排序，在需要保持相等元素相对顺序的场景中能更好地发挥作用，拓宽了选择排序算法的应用范围。
改进后的效果与应用
03
谢谢

展开更多......

收起↑