实现选择排序 题目描述：给定一个整数数组，使用选择排序算法将其按升序排列。选择排序的工作原理是每次从未排序部分找到最小元素，将其放到已排序部分的末尾。 解题过程： 基本思想 选择排序将数组分为两部分：左侧是已排序部分（初始为空），右侧是未排序部分（初始为整个数组）。算法重复以下步骤直到未排序部分为空： 在未排序部分中查找最小元素 将该最小元素与未排序部分的第一个元素交换位置 已排序部分长度增加1，未排序部分长度减少1 具体步骤 假设数组为arr，长度为n： 第1轮：在索引0到n-1范围内找到最小元素，与arr[ 0 ]交换 第2轮：在索引1到n-1范围内找到最小元素，与arr[ 1 ]交换 第3轮：在索引2到n-1范围内找到最小元素，与arr[ 2 ]交换 ... 第n-1轮：在索引n-2到n-1范围内找到最小元素，与arr[ n-2 ]交换 详细实现 以数组[ 64, 25, 12, 22, 11 ]为例： 第1轮： 未排序部分：[ 64,25,12,22,11 ]，最小元素是11（索引4） 交换arr[ 0]和arr[ 4]：数组变为[ 11,25,12,22,64 ] 第2轮： 未排序部分：[ 25,12,22,64 ]，最小元素是12（索引2） 交换arr[ 1]和arr[ 2]：数组变为[ 11,12,25,22,64 ] 第3轮： 未排序部分：[ 25,22,64 ]，最小元素是22（索引3） 交换arr[ 2]和arr[ 3]：数组变为[ 11,12,22,25,64 ] 第4轮： 未排序部分：[ 25,64 ]，最小元素是25（索引3） 交换arr[ 3]和arr[ 3 ]（实际上不需要交换） 最终得到有序数组：[ 11,12,22,25,64 ] 算法特点 时间复杂度：O(n²)，因为需要进行n-1轮比较，每轮比较n-i次 空间复杂度：O(1)，是原地排序算法 不稳定排序：相等元素的相对位置可能改变 交换次数较少：最多进行n-1次交换 优化考虑 虽然选择排序的时间复杂度固定为O(n²)，但可以通过以下方式优化： 在每轮中同时记录最小值和最大值（双向选择排序） 对于部分有序的数组，选择排序并没有优势