C 语言第34题：选择排序升序排列 n 个整数

题目

从标准输入读入 n 个整数，使用选择排序算法（Selection Sort）将其按升序排列后输出。

输入格式：第一行输入元素个数 n；第二行输入 n 个整数，以空格分隔。

输出格式：在一行中输出升序排列后的数组，元素以空格分隔，末尾换行。

数据范围与约定：1 ≤ n ≤ 1000。

思路与算法

1. 选择排序原理
外层循环 i 确定当前填入位置；内层循环在无序区间 [i, n-1] 中扫描并记录最小值的索引 min_idx。一轮扫描结束后将 a[i] 与 a[min_idx] 交换。

2. 算法特征
相比冒泡排序，选择排序的元素移动/交换次数大大减少（最多交换 n-1 次），但比较次数恒为 n(n-1)/2 次，时间复杂度恒为 O(n²)。

完整程序

#include <stdio.h>

int main(void)
{
    int n, a[500];
    if (scanf("%d", &n) != 1 || n < 1 || n > 500) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 选择排序：每轮从未排序区间 [i, n-1] 中选出最小元素的下标
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) {
                minIdx = j;
            }
        }
        // 若最小值不在当前位置 i，则执行交换
        if (minIdx != i) {
            int t = a[i];
            a[i] = a[minIdx];
            a[minIdx] = t;
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

运行示例

输入：

4
4 1 3 2

输出：

1 2 3 4