选择排序

基本概念

选择排序（Selection Sort）基本思想：
将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择最小的元素，放到已排序区间的末尾。

算法步骤

假设数组长度为n，选择排序的算法步骤如下：

1. 初始状态：已排序区间为空，未排序区间为$[0,n−1]$。
2. 第i趟选择（i从1开始）：
   1. 在未排序区间 $[i−1,n−1]$中找到最小元素的位置 $min_i$。
   2. 将位置i−1的元素与位置$min_i$的元素交换。
   3. 此时$[0,i−1]$为已排序区间，$[i,n−1]$为未排序区间。
3. 重复步骤 2，直到未排序区间为空，排序完成。

内部实现：

class Solution:
	def selectionSort(self,nums:[int])->[int]:
		n=len(nums)
		for i in range(n-1):
			min_i=i
			for j in range(i+1,n):
				if nums[j]<nums[min_i]:
					min_i=j
			if i !=min_i:
				nums[i],nums[min_i]=nums[min_i],nums[i]
		return nums
	def sortArray(self,nums:[int])->[int]:
		return self,selectionSort(nums)
		

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	$O(n^2)$	无论数组状态如何，都需要 $n(n−1)/2$​ 次比较
最坏时间复杂度	$O(n^2)$	无论数组状态如何，都需要 $n(n−1)/2$次比较
平均时间复杂度	$O(n^2)$	选择排序的时间复杂度与数据状态无关
空间复杂度	$O(1)$	原地排序，只使用常数空间
稳定性	不稳定	交换操作可能改变相等元素的相对顺序
适用场景：

• 数据量较小（n<50）
• 对空间复杂度要求严格的场景
  选择排序是一种简单直观的排序算法，通过不断选择未排序区间的最小元素来构建有序序列。
• 优点：实现简单，空间复杂度低，交换次数少
• 缺点：时间复杂度高，不适合大规模数据

应用场景：