C/C++每日一练：实现冒泡排序
题目要求
编写一个程序，实现冒泡排序算法。给定一个由 n 个整数组成的数组，要求通过冒泡排序对数组从小到大进行排序。
输入：一个整数数组，长度为 n，数组中的元素可能是正数或负数。
输出：按照升序排序后的数组。
做题思路
冒泡排序是一种简单直观的排序算法。其基本思想是通过多次遍历数组，逐步将未排序部分中的最大或最小元素“冒泡”到数组的一端，直到整个数组有序。
冒泡排序的步骤如下：
- 从数组的第一个元素开始，依次比较相邻的两个元素。如果前面的元素比后面的元素大，就交换这两个元素，确保较大的元素往右边移动。
- 每次遍历后，最大的元素被移动到未排序部分的最后一个位置。
- 重复上述过程 n-1 次（n 是数组的长度），每次遍历都将下一个最大元素移动到对应位置。
关键点：
- 冒泡排序的时间复杂度为 O(n²)，对于小规模数据比较适用，但不适合大数据集。
- 冒泡排序是稳定的排序算法，意味着相同值的元素不会改变相对顺序。
过程解析
- 初始化数组：首先定义一个待排序的整数数组，可以是用户输入或者预定义的。
- 循环遍历：外层循环控制遍历的次数，总共需要 n-1 轮；内层循环比较相邻的元素，如果前者大于后者，则进行交换。
- 优化点：如果某一轮遍历中没有发生交换，说明数组已经有序，可以提前退出循环。
- 输出结果：排序完成后，输出排好序的数组。
运用到的知识点
- 循环结构：使用双重 for 循环。
- 数组的操作：数组的遍历和相邻元素的交换。
- 条件判断：通过 if 语句判断是否需要交换元素。
- 优化技巧：利用一个标志变量（flag）来减少不必要的循环次数，用于优化算法，如果在某一轮排序中没有发生交换，则说明数组现在已经有序，无需再进行循环。
示例代码
C 实现
#include <stdio.h> // 引入标准输入输出库，用于输入输出操作 // 冒泡排序函数
void bubbleSort(int arr[], int n) { // 定义冒泡排序函数，接收一个整数数组和数组长度作为参数 int i, j; // 定义两个循环变量i和j int temp; // 定义一个临时变量，用于交换两个元素 int swapped; // 用来标记是否发生了交换，用于优化算法，如果在某一轮排序中没有发生交换，则数组已经有序，无需再进行循环// 外层循环：控制总共需要进行 n-1 轮排序 for (i = 0; i < n - 1; i++) { // 从0开始，到n-2结束，总共进行n-1轮排序 swapped = 0; // 每次循环开始时重置swapped为0，表示这一轮开始时没有发生交换 // 内层循环：逐步将最大元素“冒泡”到数组末尾 for (j = 0; j < n - i - 1; j++) { // 内层循环次数随着外层循环的进行而减少，因为最大的元素已经被冒泡到末尾 if (arr[j] > arr[j + 1]) { // 如果当前元素大于下一个元素，则进行交换 // 交换相邻元素 temp = arr[j]; // 将当前元素暂存到temp arr[j] = arr[j + 1]; // 将下一个元素赋给当前元素 arr[j + 1] = temp; // 将temp（原来的当前元素）赋给下一个元素 swapped = 1; // 发生了交换，将swapped设置为1 } } // 如果没有发生交换，说明数组已经有序，可以提前退出 if (!swapped) { // 如果swapped为0，表示这一轮排序中没有发生交换 break; // 提前退出外层循环，因为数组已经有序 } }
} // 打印数组函数
void printArray(int arr[], int n) { // 定义打印数组函数，接收一个整数数组和数组长度作为参数 for (int i = 0; i < n; i++) { // 循环遍历数组 printf("%d ", arr[i]); // 打印每个元素 } printf("\n"); // 打印换行符，使输出更加美观
} // 主函数
int main()
{ // 示例数组 int arr[] = {64, 34, 25, 12, 22, 11, 90}; // 定义一个整数数组并初始化 int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度，即数组元素个数 printf("排序前的数组：\n"); // 打印排序前的数组 printArray(arr, n); // 调用printArray函数打印数组 // 调用冒泡排序函数 bubbleSort(arr, n); // 调用bubbleSort函数对数组进行排序 printf("排序后的数组：\n"); // 打印排序后的数组 printArray(arr, n); // 调用printArray函数打印数组 return 0; // 程序正常结束，返回0
}C ++实现
#include <iostream> // 引入输入输出流库，用于输入输出操作
using namespace std; // 使用标准命名空间，避免每次调用标准库时都要加std::前缀 // 冒泡排序函数
void bubbleSort(int arr[], int n) { // 定义冒泡排序函数，接收一个整数数组和数组长度作为参数 int temp; // 定义一个临时变量，用于交换两个元素 bool swapped; // 定义一个布尔变量，用来标记是否发生了交换 // 外层循环：控制总共需要进行 n-1 轮排序 for (int i = 0; i < n - 1; i++) { // 从0开始，到n-2结束，总共进行n-1轮排序 swapped = false; // 每次循环开始时重置swapped为false，表示这一轮开始时没有发生交换 // 内层循环：逐步将最大元素“冒泡”到数组末尾 for (int j = 0; j < n - i - 1; j++) { // 内层循环次数随着外层循环的进行而减少，因为最大的元素已经被冒泡到末尾 if (arr[j] > arr[j + 1]) { // 如果当前元素大于下一个元素，则进行交换 // 交换相邻元素 temp = arr[j]; // 将当前元素暂存到temp arr[j] = arr[j + 1]; // 将下一个元素赋给当前元素 arr[j + 1] = temp; // 将temp（原来的当前元素）赋给下一个元素 swapped = true; // 发生了交换，将swapped设置为true }}// 如果没有发生交换，说明数组已经有序，可以提前退出 if (!swapped) { // 如果swapped为false，表示这一轮排序中没有发生交换 break; // 提前退出外层循环，因为数组已经有序 }}
}// 打印数组函数
void printArray(int arr[], int n) { // 定义打印数组函数，接收一个整数数组和数组长度作为参数 for (int i = 0; i < n; i++) { // 循环遍历数组 cout << arr[i] << " "; // 打印每个元素，元素之间用空格分隔 }cout << endl; // 打印换行符，使输出更加美观
}// 主函数
int main()
{// 示例数组 int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; // 定义一个整数数组并初始化 int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度，即数组元素个数 cout << "排序前的数组：" << endl; // 打印提示信息，表示接下来将打印排序前的数组 printArray(arr, n); // 调用printArray函数打印数组 // 调用冒泡排序函数 bubbleSort(arr, n); // 调用bubbleSort函数对数组进行排序 cout << "排序后的数组：" << endl; // 打印提示信息，表示接下来将打印排序后的数组 printArray(arr, n); // 调用printArray函数打印数组 return 0; // 程序正常结束，返回0
}