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)。

与冒泡排序怎么选

当教学目标是理解“比较与交换是不同成本”时,选择排序非常直观。它也适合数据量很小、实现简单优先,或写入成本明显高于比较成本的场景。

如果数据已经接近有序,选择排序仍然要完成几乎全部比较,无法利用这种有序性。此时插入排序通常更合适。对于较大规模数据,实际工程中也通常会选择平均复杂度更低的排序算法,而不是依赖选择排序的低交换次数。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

选择排序怎样减少交换次数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通