选择排序
入门比较次数固定，交换次数少，适合理解「选择-放置」策略。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void selectionSort(int arr[], int n) {
2 for (int i = 0; i < n - 1; i++) {
3 int minIdx = i;
4 for (int j = i + 1; j < n; j++) {
5 if (arr[j] < arr[minIdx]) {
6 minIdx = j;
7 }
8 }
9 if (minIdx != i) {
10 int temp = arr[i];
11 arr[i] = arr[minIdx];
12 arr[minIdx] = temp;
13 }
14 }
15}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n²)
最坏 O(n²)
算法讲解
选择排序将数组分为已排序和未排序两部分，初始已排序部分为空。
每轮在未排序部分中找到最小元素，与未排序部分的第一个元素交换。
经过 n-1 轮后，数组完全有序。
时间复杂度 O(n²)，无论输入如何比较次数都是 n(n-1)/2 次。