NO.22 十六届蓝桥杯备战 | 一维数组 | 七道练习 | 冒泡排序 (C++)

目录

1. 前言
2. 一维数组基础知识
   • 一维数组定义
   • 一维数组的初始化
   • 一维数组的遍历
   • 一维数组的应用场景
3. 七道练习
   • 练习1：数组求和
   • 练习2：数组反转
   • 练习3：数组最大值和最小值
   • 练习4：数组去重
   • 练习5：二维数组转置
   • 练习6：冒泡排序实现
   • 练习7：冒泡排序优化
4. 冒泡排序原理
   • 冒泡排序基本原理
   • 冒泡排序的时间复杂度分析
5. C++中如何实现冒泡排序
   • 冒泡排序的代码实现
   • 冒泡排序优化后的代码实现
6. 冒泡排序的应用场景
   • 冒泡排序在实际场景中的应用
7. 总结与提升
8. 附录
   • C++代码规范
   • C++数组常见错误及解决方法

---

1. 前言

在备战蓝桥杯的过程中，掌握一维数组以及基本排序算法的实现是至关重要的。尤其是冒泡排序，这是一种非常基础且简单的排序算法，在大多数编程竞赛中都会遇到。本文将通过七道练习带领大家全面掌握一维数组的操作技巧，同时着重讲解冒泡排序的实现和优化方法。

2. 一维数组基础知识

一维数组定义

在C++中，数组是用来存储多个相同类型数据的数据结构。一维数组是最简单的数组形式，它可以用来存储一系列按顺序排列的数据。数组的元素在内存中是连续存储的。

定义一个一维数组的基本语法如下：

cppCopy Code
type array_name[size];

• type：表示数组元素的类型（如 int、float、char等）。
• array_name：数组的名字。
• size：数组的大小，表示数组中元素的个数。

示例：

cppCopy Code
int arr[5];  // 声明一个包含5个整数的数组

一维数组的初始化

在C++中，可以通过以下几种方式来初始化一维数组：

1. 显式初始化： 通过大括号 {} 将数组中的元素进行初始化。

   cppCopy Code
   int arr[5] = {1, 2, 3, 4, 5};
   

2. 部分初始化： 如果初始化元素少于数组大小，剩余的元素会自动被初始化为零。

   cppCopy Code
   int arr[5] = {1, 2};  // 其余元素为0
   

3. 隐式初始化： 如果不进行初始化，C++会为数组元素分配默认值，局部变量默认值不确定（例如垃圾值），而静态数组则会被初始化为零。

   cppCopy Code
   int arr[5];  // 数组元素未初始化
   

一维数组的遍历

遍历数组是对数组操作中最常见的需求。可以通过索引来访问数组的每个元素。

示例：

cppCopy Code
int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; ++i) {
    cout << arr[i] << " ";  // 输出数组元素
}

一维数组的应用场景

一维数组常用于存储具有相同类型的数据，如成绩单、温度数据、价格数据等。在编程竞赛中，数组常用于存储输入数据并对其进行处理，比如排序、查找最大值、最小值等。

3. 七道练习

练习1：数组求和

给定一个一维数组，编写程序计算数组中所有元素的和。

思路：

通过遍历数组，将每个元素相加。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int sum = 0;
    
    for (int i = 0; i < 5; ++i) {
        sum += arr[i];  // 累加数组元素
    }
    
    cout << "数组元素的和为：" << sum << endl;
    return 0;
}

练习2：数组反转

给定一个数组，编写程序将其反转。

思路：

可以使用两个指针分别指向数组的首尾，交换两个元素，直到指针相遇。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    
    int left = 0, right = 4;
    while (left < right) {
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
    
    cout << "反转后的数组为：";
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

练习3：数组最大值和最小值

给定一个数组，编写程序找出其中的最大值和最小值。

思路：

通过遍历数组，记录当前最大和最小值。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    
    int max_val = arr[0];
    int min_val = arr[0];
    
    for (int i = 1; i < 5; ++i) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }
    
    cout << "最大值：" << max_val << endl;
    cout << "最小值：" << min_val << endl;
    
    return 0;
}

练习4：数组去重

给定一个数组，编写程序去除数组中的重复元素。

思路：

通过遍历数组，将不重复的元素保存到另一个数组中。

代码实现：

cppCopy Code
#include <iostream>
#include <set>
using namespace std;

int main() {
    int arr[8] = {1, 2, 2, 3, 4, 4, 5, 5};
    set<int> unique_elements;
    
    for (int i = 0; i < 8; ++i) {
        unique_elements.insert(arr[i]);
    }
    
    cout << "去重后的数组为：";
    for (int val : unique_elements) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

练习5：二维数组转置

将一个二维数组转置为另一二维数组。

思路：

将第i行第j列的元素转置到第j行第i列。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

int main() {
    int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int transposed[3][2];
    
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            transposed[j][i] = arr[i][j];
        }
    }
    
    cout << "转置后的数组为：" << endl;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 2; ++j) {
            cout << transposed[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

练习6：冒泡排序实现

冒泡排序是一种简单的排序算法，其原理是通过重复交换相邻的元素，将最大的元素"冒泡"到数组的末尾。

思路：

从数组的开始位置依次比较相邻的元素，如果前面的元素大于后面的元素，则交换它们的位置，直到整个数组排序完成。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < n-i-1; ++j) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    int arr[5] = {5, 3, 8, 4, 2};
    
    bubbleSort(arr, 5);
    
    cout << "排序后的数组为：";
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

练习7：冒泡排序优化

冒泡排序的时间复杂度是O(n^2)，但可以通过优化来减少不必要的遍历次数。具体来说，如果在某一轮遍历中没有发生交换，说明数组已经有序，可以提前结束排序过程。

思路：

引入一个标志变量，记录某一轮是否发生了交换。如果没有交换，则提前结束排序。

代码实现：

cppCopy Code
#include <iostream>
using namespace std;

void optimizedBubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; ++i) {
        bool swapped = false;
        
        for (int j = 0; j < n-i-1; ++j) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        
        if (!swapped) {
            break;  // 提前结束
        }
    }
}

int main() {
    int arr[5] = {5, 3, 8, 4, 2};
    
    optimizedBubbleSort(arr, 5);
    
    cout << "优化后的排序数组为：";
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

4. 冒泡排序原理

冒泡排序基本原理

冒泡排序是一种简单的排序算法，通过不断交换相邻的元素，使得每一轮遍历都能将未排序部分的最大元素"冒泡"到数组的末尾。这样经过多轮交换后，整个数组就会变得有序。

冒泡排序的时间复杂度分析

• 最坏情况：时间复杂度为O(n^2)，此时数组是逆序的，需要进行最多的交换。
• 最佳情况：时间复杂度为O(n)，当数组已经有序时，只需要进行一轮遍历。