排序算法——选择排序

一、先容

「排序算法sortingalgorithm」用于对一组数据按照特定次序举行排列。排序算法有着广泛的应用，由于有序数据通常可以大概被更有用地查找、分析和处置惩罚。
如图所示，排序算法中的数据范例可以是整数、浮点数、字符或字符串等。排序的判定规则可根据需求设定，如数字巨细、字符ASCII码次序或自界说规则。

二、评价维度

1.运行服从：我们盼望排序算法的时间复杂度只管低，且总体操纵数目较少（即时间复杂度中的常数项低落）。对于大数据量环境，运行服从显得尤为告急。
2.就地性：顾名思义，「原地排序」通过在原数组上直接操纵实现排序，无须借助额外的辅助数组，从而节流内存。通常环境下，原地排序的数据搬运操纵较少，运行速率也更快。
3.稳固性：「稳固排序」在完成排序后，相当元素在数组中的相对次序不发生改变。稳固排序是多级排序场景的须要条件。假设我们有一个存储门生信息的表格，第1列和第2列分别是姓名和年事。在这种环境下，「非稳固排序」大概导致输入数据的有序性丧失。
# 输入数据是按照姓名排序好的
# (name, age)
('A', 19)
('B', 18)
('C', 21)
('D', 19)
('E', 23)
# 假设使用非稳固排序算法按年事排序列表，
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
# 输入数据按姓名排序的性子丢失
('B', 18)
('D', 19)
('A', 19)
('C', 21)
('E', 23)
4.自顺应性：「自顺应排序」的时间复杂度会受输入数据的影响，即最佳、最差、匀称时间复杂度并不完全相当。 自顺应性必要根据具体环境来评估。假如最差时间复杂度差于匀称时间复杂度，分析排序算法在某些数据下性能大概劣化，因此被视为负面属性；而假如最佳时间复杂度优于匀称时间复杂度，则被视为正面属性。
5.是否基于比力：「基于比力的排序」依赖于比力运算符（）来判定元素的相对次序，从而排序整个数组，理论最优时间复杂度为𝑂(𝑛log𝑛)。而「非比力排序」倒霉用比力运算符，时间复杂度可达𝑂(𝑛)， 但其通用性相对较差。
理想排序算法
运行快、原地、稳固、正向自顺应、通用性好。显然，迄今为止尚未发现兼具以上全部特性的排序算法。因此，在选择排序算法时，必要根据具体的数据特点和题目需求来决定。
三、选择排序

1.实现原理

「选择排序selectionsort」的工作原理非常直接：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末端。设数组的长度为𝑛，选择排序的算法流程如下所示：
1. 初始状态下，全部元素未排序，即未排序（索引）区间为[0,𝑛−1]。
2. 选取区间[0,𝑛−1]中的最小元素，将其与索引0处元素交换。完成后，数组前1个元素已排序。
3. 选取区间[1,𝑛−1]中的最小元素，将其与索引1处元素交换。完成后，数组前2个元素已排序。
4. 以此类推。颠末𝑛−1轮选择与交换后，数组前𝑛−1个元素已排序。
5. 仅剩的一个元素肯定是最大元素，无须排序，因此数组排序完成。
2.代码

2. def selection_sort(nums: list[int]):
3.     """ 选择排序"""
4.     n = len(nums)
5.     # 外循环：未排序区间为 [i, n-1]
6.     for i in range(n-1):
7.         # 内循环：找到未排序区间内的最小元素
8.         k = i
9.         for j in range(i + 1, n):
10.             if nums[j] < nums[k]:
11.                 k = j # 记录最小元素的索引
12.         # 将该最小元素与未排序区间的首个元素交换
13.         nums[i], nums[k] = nums[k], nums[i]
15. nums = [5, 2, 4, 6, 1, 3]
16. selection_sort(nums)
17. print(nums)

复制代码

3.算法特性

‧ 时间复杂度为𝑂(

)、非自顺应排序：外循环共𝑛−1轮，第一轮的未排序区间长度为𝑛，末了一轮 的未排序区间长度为2，即各轮外循环分别包罗𝑛、𝑛−1、…、3、2轮内循环，求和为(𝑛−1)(𝑛+2)/2
‧ 空间复杂度𝑂(1)、原地排序：指针𝑖和𝑗使用常数巨细的额外空间。
‧ 非稳固排序：如图所示，元素nums 有大概被交换至与其相当的元素的右边，导致两者相对次序发生改变。