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

题目

选择排序升序排列 n 个整数

思路

外 i 从 0 到 n-2，内层找 [i,n-1] 最小下标 k，与 a[i] 交换。

解题分析

选择排序每轮找最小下标与 i 交换，交换次数通常少于冒泡。比较次数仍是 O(n²)，与第 33 题对照理解差异。

完整程序

#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]);
    }
    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;
            }
        }
        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