[蓝桥杯]实现选择排序

实现选择排序

题目描述

实现选择排序算法。介绍如下：

选择排序的工作原理是每一次从需要排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排列完毕。

请编写代码，完成选择排序，对给定数据进行升序排列

输入描述

第一行，数字 N (2≤N≤100)N (2≤N≤100),表示待排序的元素个数。

第二行，待排序的元素。

输出描述

输出一行，为升序序列。

输入输出样例

示例

输入

6
7 1 4 8 5 2

输出

1 2 4 5 7 8

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 7780  |  总提交次数: 8170  |  通过率: 95.2%

难度: 中等   标签: 排序

算法原理详解

1. ​​初始化​​：从数组第一个元素开始遍历
2. ​​查找最小值​​：在未排序部分（i+1 到 n-1）中查找最小元素
3. ​​交换位置​​：将找到的最小元素与当前位置 i 的元素交换
4. ​​迭代推进​​：重复上述过程直到整个数组有序

时间复杂度分析

• ​​比较次数​​：固定为 2n(n−1)​ 次
• ​​交换次数​​：最多 n−1 次
• ​​时间复杂度​​：O(n2)（最优/最坏/平均情况相同）

算法特性

• ​​不稳定排序​​：可能改变相等元素的原始顺序（如序列 5, 8, 5, 2）
• ​​原地排序​​：仅需 O(1) 额外空间
• ​​适用场景​​：小规模数据或对内存限制严格的情况

  #include <iostream>
  using namespace std;
  
  void selectionSort(int arr[], int n) {
      for (int i = 0; i < n - 1; i++) {
          int minIndex = i;  // 记录最小元素位置
          for (int j = i + 1; j < n; j++) {
              if (arr[j] < arr[minIndex]) {
                  minIndex = j;  // 更新最小元素位置
              }
          }
          // 交换最小元素到正确位置
          swap(arr[i], arr[minIndex]);
      }
  }
  
  int main() {
      int n;
      cin >> n;
      int arr[n];
      
      for (int i = 0; i < n; i++) {
          cin >> arr[i];
      }
      
      selectionSort(arr, n);
      
      // 输出排序结果
      for (int i = 0; i < n - 1; i++) {
          cout << arr[i] << " ";
      }
      cout << arr[n - 1];  // 最后一个元素单独输出避免末尾空格
      
      return 0;
  }

  示例演示（输入：7 1 4 8 5 2）

  步骤	操作	当前数组状态
  初始	-	[7, 1, 4, 8, 5, 2]
  1	最小元素1与7交换	[​​1​​, 7, 4, 8, 5, 2]
  2	最小元素2与7交换	[1, ​​2​​, 4, 8, 5, 7]
  3	4已是未排序最小	[1, 2, ​​4​​, 8, 5, 7]
  4	最小元素5与8交换	[1, 2, 4, ​​5​​, 8, 7]
  5	最小元素7与8交换	[1, 2, 4, 5, ​​7​​, 8]

  输出结果：1 2 4 5 7 8