就算经历各番碰撞，幸运也将一直站在我这边
—— 25.5.18
一、引言
选择排序(Selection Sort) 是一种简单直观的排序算法。它首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
二、算法思想
第一步：在未排序序列中找到最小(大)元素，存放到排序序列的起始位置。
第二步：再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕
三、算法分析
1.时间复杂度
T(n) = O(n ^ 2)
2.空间复杂度
S(n) = O(1)
四、选择排序的优缺点
1.选择排序的优点
① 简单易懂
选择排序是一种简单直观的排序算法，容易理解和实现。
② 原地排序
选择排序不需要额外的存储空间，只使用原始数组进行排序
③ 适用于小型数组
对于小型数组，选择排序的性能表现较好。
2.选择排序的缺点
① 时间复杂度高
在处理大规模数据时效率较低
② 不稳定
选择排序在排序过程中可能会改变相同元素的相对顺序，因此它是一种不稳定的算法
3.优化方案
【选择排序】在众多排序算法中效率较低，时间复杂度为 O(n^2)
当有 n = 100000 个数字。即使我们的计算机速度超快，并且可以在1秒内计算 10^8 次操作，但选择排序仍需要大约一百秒才能完成。
每一个内层循环是从一个区间中找到一个最小值，并且更新这个最小值。是一个【动态区间最值 】问题，所以这一步，我们是可以通过【线段树】来优化的。这样就能将内层循环的时间复杂度优化成 O(log2n) 了，总的时间复杂度就变成了 O(nlog2n)。常见的选择排序优化是采用堆排序来进行优化
五、实战练习
选择排序的代码实现
选择排序的核心思想是每轮选择剩余元素中的最小（大）值，并将其放到已排序部分的末尾。
选择排序后的列表（数组）应遵守小（大）的在前，大（小）的在后的升（降）序顺序
def selectionSort(arr:List) —> arr:List
n = len(arr)
for i in range(n):
min = i
for j in range(i + 1, n):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]75. 颜色分类
给定一个包含红色、白色和蓝色、共
n个元素的数组nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数
0、1和2分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
思路与算法
① 遍历数组
外层循环 i 从 0 到 n-1（n 为数组长度），表示当前待排序的位置。
② 寻找最小值
初始化 min = i，假设当前位置 i 的元素最小。内层循环 j 从 i+1 到 n-1，比较 arr[j] 与 arr[min]：若 arr[j] < arr[min]，更新 min = j（记录更小值的索引）。
③ 交换元素
内层循环结束后，将 arr[i] 与 arr[min] 交换，确保位置 i 为当前最小值。
④ 重复
外层循环继续，逐步将剩余元素中的最小值放到正确位置。
class Solution:
def selectionSort(self, arr: List[int]):
n = len(arr)
for i in range(n):
min = i
for j in range(i + 1, n):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
self.selectionSort(nums)
4. 寻找两个正序数组的中位数
给定两个大小分别为
m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数 。示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
思路与算法
① 合并数组
将 nums2 中的所有元素逐个添加到 nums1 的末尾。此时 nums1 包含两个数组的所有元素，但无序。
② 排序合并后的数组
使用选择排序对 nums1 进行排序，选择排序的时间复杂度为 O ((m+n)²)，其中 m 和 n 分别是两个数组的长度。
③ 计算中位数
设合并后数组的长度为 total_length。
奇数长度：直接返回中间元素 nums1[total_length // 2]。
偶数长度：返回中间两个元素的平均值 (nums1[total_length//2 - 1] + nums1[total_length//2]) / 2.0。
class Solution:
def selectionSort(self, arr: List[int]):
n = len(arr)
for i in range(n):
min = i
for j in range(i + 1, n):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
for x in nums2:
nums1.append(x)
n = len(nums1)
self.selectionSort(nums1)
if n % 2 == 1:
return nums1[n // 2]
return (nums1[n // 2 - 1] + nums1[n // 2]) / 2.0
747. 至少是其他数字两倍的最大数
给你一个整数数组
nums，其中总是存在 唯一的 一个最大整数 。请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回
-1。示例 1：
输入：nums = [3,6,1,0] 输出：1 解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。示例 2：
输入：nums = [1,2,3,4] 输出：-1 解释：4 没有超过 3 的两倍大，所以返回 -1 。提示：
2 <= nums.length <= 500 <= nums[i] <= 100nums中的最大元素是唯一的
思路与算法
① 寻找最大值索引
遍历数组 nums，记录最大值的索引 max。
② 排序数组
使用选择排序对 nums 进行升序排列。
③ 比较最大元素与次大元素
排序后，最大元素位于 nums[-1]，次大元素位于 nums[-2]。
④ 检查最大元素是否至少是次大元素的两倍
若是，返回之前记录的最大值索引 max。否则，返回 -1。
class Solution:
def selectionSort(self, arr: List[int]):
n = len(arr)
for i in range(n):
min = i
for j in range(i + 1, n):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
def dominantIndex(self, nums: List[int]) -> int:
max = 0
n = len(nums)
for i in range(n):
if nums[i] > nums[max]:
max = i
self.selectionSort(nums)
maxCount = nums[-1]
subMaxCount = nums[-2]
if maxCount >= 2 * subMaxCount:
return max
return -1
