Java第33题：冒泡排序升序排列 n 个整数

题目

冒泡排序升序排列 n 个整数

思路

双层循环：外 i 控制轮数，内 j 比较 a[j] 与 a[j+1]，逆序则交换；可加标志位某轮无交换则提前停。

解题分析

冒泡每轮把当前最大值换到末尾，最好情况（已有序）仍要比较很多对。选择排序每轮只确定一个最小位置，交换次数通常更少，但比较次数仍是 O(n²)。

完整程序

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++)
        for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) {
            int t = a[j];
            a[j] = a[j + 1];
            a[j + 1] = t;
        }
        for (int i = 0; i < n; i++) System.out.print(a[i] + (i + 1 < n ? " " : "\n"));
    }
}

运行示例

输出：

1 2 3 4

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

Arrays.sort

程序：

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;
        }
        Arrays.sort(a);
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + (i + 1 < n ? " " : "\n"));
        }
    }
}

运行示例

输出：

1 2 3 4