C 语言第33题：冒泡排序升序排列 n 个整数

题目

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

思路

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

解题分析

冒泡每轮把当前最大值换到末尾，最好情况（已有序）仍要比较很多对。选择排序每轮只确定一个最小位置，交换次数通常更少，但比较次数仍是 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]);
    }
    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++) {
        printf("%d%c", a[i], i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

运行示例

输入：

4
4 1 3 2

输出：

1 2 3 4

其它写法

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

插入排序

与正文冒泡对比，近乎有序时往往更快。

程序：

#include <stdio.h>

int main(void)
{
    int n, a[500];
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    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