Java第34题：选择排序升序排列 n 个整数

题目

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

思路

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

解题分析

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

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 4;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = 4;
        for (int i = 0; i < n - 1; i++) {
            int mi = i;
            for (int j = i + 1; j < n; j++) if (a[j] < a[mi]) mi = j;
            if (mi != i) {
                int t = a[i];
                a[i] = a[mi];
                a[mi] = t;
            }
        }
        for (int i = 0; i < n; i++) System.out.print(a[i] + (i + 1 < n ? " " : "\n"));
    }
}

运行示例

输出：

1 2 3 4