深高北-L15-冒泡&选择排序

张kk

2026-03-21 02:15:00

发布于：广东

33阅读

0回复

0点赞

冒泡排序

基本思想

通过相邻元素的比较和交换，每一轮将最大（或最小）的元素“冒泡”到序列的末端。

排序过程

轮次	操作	说明
第1轮	相邻比较，交换逆序对	将最大值放到最后
第2轮	重复上述过程	将次大值放到倒数第二位
...	...	...
第n-1轮	最后两个元素比较	排序完成

代码实现（下标从1开始，输入n个数据）

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                          // 输入数据个数
    
    int arr[100];                      // 假设最多100个数据
    for (int i = 1; i <= n; i++) {     // 从下标1开始输入
        cin >> arr[i];
    }
    
    // 冒泡排序
    for (int i = 1; i <= n - 1; i++) {           // 共 n-1 轮
        for (int j = 1; j <= n - i; j++) {       // 每轮比较次数递减
            if (arr[j] > arr[j + 1]) {           // 相邻元素比较
                swap(arr[j], arr[j + 1]);        // 交换
            }
        }
    }
    
    // 输出排序结果
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

示例演示

初始数组	5	3	8	1	2
第1轮后	3	5	1	2	8
第2轮后	3	1	2	5	8
第3轮后	1	2	3	5	8
第4轮后	1	2	3	5	8

选择排序

基本思想

每一轮从待排序序列中选出最小（或最大）的元素，放到已排序序列的末尾。

排序过程

轮次	操作	说明
第1轮	扫描整个数组，找到最小值	与第一个元素交换
第2轮	从第二个元素开始扫描，找到最小值	与第二个元素交换
...	...	...
第n-1轮	最后两个元素比较	排序完成

代码实现（下标从1开始，输入n个数据）

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                          // 输入数据个数
    
    int arr[100];                      // 假设最多100个数据
    for (int i = 1; i <= n; i++) {     // 从下标1开始输入
        cin >> arr[i];
    }
    
    // 选择排序
    for (int i = 1; i <= n - 1; i++) {           // 共 n-1 轮
        int k= i;                        // 假设当前位置为最小值
        for (int j = i + 1; j <= n; j++) {       // 在未排序部分找最小值
            if (arr[j] < arr[k]) {
                k= j;                    // 更新最小值下标
            }
        }
        if (k!= i) {                     // 如果最小值不是当前位置
            swap(arr[i], arr[k]);         // 交换
        }
    }
    
    // 输出排序结果
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}