hnust 1816: 算法10-9：简单选择排序
题目描述
选择排序的基本思想是：每一趟比较过程中，在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。
在多种选择排序中，最常用且形式最为简单的是简单选择排序。
简单选择排序的算法可以描述如下：
在本题中，读入一串整数，将其使用以上描述的简单选择排序的方法从小到大排序，并输出。
输入
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
输出
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入 Copy
10
2 8 4 6 1 10 7 3 5 9
样例输出 Copy
1 2 3 4 5 6 7 8 9 10
提示
在本题中，需要按照题目描述中的算法完成简单选择排序的算法。
简单选择排序是一种思路非常简单，结构简洁的排序算法。它的特点是，无论记录的初始排列形式如何，所需进行的关键字间的比较次数始终相同，均为n(n-1)/2。因此，其时间复杂度也固定在O(n2)。
解题过程
这段代码实现了选择排序（Selection Sort）算法，选择排序是一种简单直观的排序算法，其工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序数据元素排完。以下是对代码的详细解析：
-
函数定义：
selectSort(int a[], int len)：这是选择排序的函数，接收一个整数数组a和数组的长度len作为参数。
-
外层循环：
for(int i = 0; i < len - 1; i++)：外层循环控制排序过程中已排序元素的索引，从0开始，直到倒数第二个元素。
-
选择最小元素：
int p = i;：初始化一个变量p作为当前轮次中已找到的最小元素的索引。
-
内层循环：
for(int j = i + 1; j < len; ++j)：内层循环从i + 1开始，遍历当前未排序的部分，寻找最小元素。
-
更新最小元素索引：
if(a[j] < a[p]) p = j;：如果在内层循环中找到一个比当前最小元素a[p]更小的元素a[j]，则更新p为j。
-
交换元素：
swap(a[i], a[p]);：内层循环结束后，将找到的最小元素a[p]与当前轮次的第一个元素a[i]交换位置。
-
swap函数：- 代码中没有给出
swap函数的实现，但它应该是一个交换两个数组元素的函数。
- 代码中没有给出
-
算法性能：
- 选择排序的时间复杂度是 O(n^2)，其中 n 是数组的长度。这是因为算法需要进行两层循环，内层循环在最坏情况下会遍历所有剩余的元素。
-
稳定性：
- 选择排序是稳定的排序算法，因为它不会改变相同元素之间的顺序。
-
适用场景：
- 选择排序适用于数据量较小或者数据基本有序的情况，此时它的效率相对较高。
选择排序是一种基础的排序算法，由于其实现简单，它在实际编程中仍然有着广泛的应用。然而，对于大规模数据集，更高效的排序算法（如快速排序、归并排序等）可能是更好的选择。
AC代码
#include <bits/stdc++.h>
using namespace std;int a[1010];
void selectSort(int a[], int len){for(int i = 0;i < len - 1;i++){int p = i;for(int j = i + 1;j < len;++j) if(a[j] < a[p]) p=j;swap(a[i], a[p]);}
}
int main(){int n;cin >> n;for(int i = 0;i < n;i++) cin >> a[i]; selectSort(a, n);for(int i = 0;i < n;i ++) cout << a[i] << ' ';return 0;
}
