C / C++ / 系统课时
选择排序怎样减少交换次数
选择排序怎样减少交换次数
选择排序的关键优势不是“比较得少”,而是每一轮只记录最小元素的位置,扫描结束后最多交换一次。本课通过 C 语言实现选择排序,并与冒泡排序在同一组数据上统计比较和交换次数,观察两个指标为什么必须分开分析。
学习目标
- 实现选择排序,并正确维护每轮的最小元素下标。
- 区分比较次数与交换次数,理解选择排序减少写入操作的原因。
- 能根据数据规模和写入成本判断选择排序是否合适。
选择排序怎样工作
对长度为 n 的数组,选择排序把数组分成“已排序区”和“未排序区”。第 i 轮在区间 i...n-1 中寻找最小值,只保存它的下标;这一轮扫描结束后,如果最小值不在位置 i,再交换一次。

因此,选择排序在比较阶段不会频繁移动元素。即使最小值不断更新,也只是修改 minIndex 变量;真正的数据交换推迟到该轮结束。
用代码统计比较与交换
下面同时实现选择排序和冒泡排序。两种实现都按相同规模完成比较,以便直接观察交换次数的差异。
c
#include <stdio.h>
#include <stddef.h>
typedef struct {
int comparisons;
int swaps;
} Stats;
static void swap_int(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
static Stats selection_sort(int arr[], size_t n) {
Stats stats = {0, 0};
/* 每轮确定一个最终位置,左侧区域随之扩大。 */
for (size_t i = 0; i + 1 < n; ++i) {
size_t min_index = i;
for (size_t j = i + 1; j < n; ++j) {
++stats.comparisons;
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
/* 一轮扫描完成后最多交换一次。 */
if (min_index != i) {
swap_int(&arr[i], &arr[min_index]);
++stats.swaps;
}
}
return stats;
}
static Stats bubble_sort(int arr[], size_t n) {
Stats stats = {0, 0};
/* 每轮把当前最大值逐步交换到区间末尾。 */
for (size_t end = n; end > 1; --end) {
for (size_t j = 0; j + 1 < end; ++j) {
++stats.comparisons;
if (arr[j] > arr[j + 1]) {
swap_int(&arr[j], &arr[j + 1]);
++stats.swaps;
}
}
}
return stats;
}
static void print_array(const int arr[], size_t n) {
for (size_t i = 0; i < n; ++i) {
printf("%d%s", arr[i], i + 1 == n ? "\n" : " ");
}
}
int main(void) {
int a[] = {64, 25, 12, 22, 11};
int b[] = {64, 25, 12, 22, 11};
size_t n = sizeof(a) / sizeof(a[0]);
Stats selection = selection_sort(a, n);
Stats bubble = bubble_sort(b, n);
printf("selection: ");
print_array(a, n);
printf("comparisons=%d, swaps=%d\n", selection.comparisons, selection.swaps);
printf("bubble: ");
print_array(b, n);
printf("comparisons=%d, swaps=%d\n", bubble.comparisons, bubble.swaps);
return 0;
}预期输出
text
selection: 11 12 22 25 64
comparisons=10, swaps=3
bubble: 11 12 22 25 64
comparisons=10, swaps=9这里两种实现都进行了 10 次比较,但选择排序只交换 3 次,而冒泡排序交换了 9 次。结果说明“比较少”和“交换少”是两个不同的优化目标。
为什么交换次数会更少
选择排序一共执行 n - 1 轮,每轮最多交换一次,因此交换次数上限是 n - 1。冒泡排序则可能在一次扫描中发生多次相邻交换;逆序数组的交换次数可达到 n * (n - 1) / 2。
这并不意味着选择排序的时间复杂度更低。无论输入是否已经有序,寻找每轮最小值都要继续扫描剩余元素,所以比较次数固定为 n * (n - 1) / 2,时间复杂度仍为 O(n^2)。
与冒泡排序怎么选
当教学目标是理解“比较与交换是不同成本”时,选择排序非常直观。它也适合数据量很小、实现简单优先,或写入成本明显高于比较成本的场景。
如果数据已经接近有序,选择排序仍然要完成几乎全部比较,无法利用这种有序性。此时插入排序通常更合适。对于较大规模数据,实际工程中也通常会选择平均复杂度更低的排序算法,而不是依赖选择排序的低交换次数。
按自己的节奏,确认真正理解。