选择排序：C 语言函数137

选择排序是一种简单的排序算法，它通过重复地从未排序列表中选择最小元素并将其放置到列表的开头来对列表进行排序。算法的复杂度为 O(n^2)，其中 n 是列表中的元素数量。

C 语言实现

以下是 C 语言中选择排序的实现：```c
#include
void selection_sort(int arr[], int n) {
int i, j, min_idx;
// 遍历数组中的所有元素
for (i = 0; i < n-1; i++) {
// 查找最小元素的索引
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将最小元素与第 i 个元素交换
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
```

算法步骤

选择排序算法的步骤如下：1. 从未排序列表中选择最小元素。
2. 将最小元素与当前正在考虑的第一个未排序元素互换。
3. 重复步骤 1 和 2，直到所有元素都被排序。

时间复杂度

选择排序的时间复杂度为 O(n^2)。这是因为算法需要遍历列表 n 次，每次遍历需要花费 O(n) 时间来查找最小元素。因此，总的时间复杂度为 O(n^2)。

优点和缺点

优点：

* 简单易懂。
* 在小数据集上性能良好。

缺点：

* 在大数据集上效率低下。
* 不稳定，即相等元素在排序后可能不会保持相同的顺序。

应用

选择排序通常用于对小数据集排序，或作为教育目的的教学工具。它也可以用于解决以下问题：* 查找数组中的最小或最大元素。
* 找出数组中第 k 个最大的元素。

2024-12-04

---

上一篇：C 语言中 rand() 函数

下一篇：C 语言位操作函数