[C/C++]排序算法1、冒泡排序
排序算法将一串数组（一个列表）中的元素（整数，数字，字符串等）按某种顺序（增大，减小，字典顺序等）重新排列。
有很多种不同的排序算法，每一种都有各自的优势和限制。
排序常常作为计算机课程中的经典性问题，用以了解一系列排序的算法思路。
我们以最简单的冒泡排序开头，分析一下它的时间复杂度和稳定性。
冒泡上课记录：
#include <iostream>
using namespace std;
int main(){
//int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
//int arr[] = {1, 2, 3,4, 5, 6, 7, 8};
int arr[] = {1, 3, 2,4, 5, 6, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "排序前的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
int cont=0;
int jh_cont=0;
bool jiaohuan;
// 3 2 2(1) 4 1
// 2 3 2(1) 4 1
// 2 2(1) 3 4 1
// 2 2(1) 3 4 1
//2 2(1) 3 1 4
//2 2(1) 1 3 4
//2 1 2（1） 3 4
//1 2 2（1） 3 4
//稳定算法
for (int i = 0; i < n - 1; i++) {
jiaohuan = false;
for (int j = 0; j < n - i - 1; j++) {
cont++;
if (arr[j] > arr[j + 1]) {
jiaohuan=true;
jh_cont++;
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//这一轮下来没有发生交换
if(jiaohuan==false){
break;
}
}
cout << "排序后的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout<<"一共执行了"<<cont;
cout<<"一共交换了"<<jh_cont;
cout << endl;
}1. 代码功能
我们以小白新手的角度来完整的介绍代码，不管你在哪个段位，都可以快速的查漏补缺。这段 C++ 代码主要实现了冒泡排序算法，并对排序过程中的比较次数和交换次数进行了统计，最后输出排序前后的数组以及比较和交换的次数。
2. 代码具体分析
2.1 头文件与命名空间
#include <iostream>
using namespace std;
- 首先引入了
<iostream>头文件，用于实现输入输出操作，比如通过cout输出信息到控制台。 - 使用了
using namespace std;语句，这使得在代码中可以直接使用标准库中的名字（如cout、endl等）而无需加上std::前缀。不过在实际的大型项目开发中，为了避免命名冲突，通常不建议这样全局使用命名空间，而是按需使用std::来指定具体的标准库元素。
2.2 数组定义与初始化
//int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
//int arr[] = {1, 2, 3,4, 5, 6, 7, 8};
int arr[] = {1, 3, 2,4, 5, 6, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
这里定义了一个整型数组arr，并通过注释展示了可以初始化数组的不同示例值。当前使用的初始化值为{1, 3, 2,4, 5, 6, 7, 8}。
这里进行了多个测试，可以依次的把注释打开进行尝试，了解不同数据状态下，他们执行的次数。
通过sizeof(arr) / sizeof(arr[0])计算出数组arr的元素个数，并将结果存储在变量n中。这种方式可以在不知道数组具体长度的情况下准确获取其元素个数，是 C 和 C++ 中常用的技巧。
2.3 排序前数组输出
cout << "排序前的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
这段代码使用循环遍历数组arr，并通过cout将数组中的每个元素依次输出到控制台，在输出之前先输出了提示信息 “排序前的数组：”，以便清晰地展示排序前后的数组状态。
2.4 冒泡排序核心逻辑及比较、交换次数统计
- 首先定义了三个变量：
cont用于统计比较次数，初始化为 0；jh_cont用于统计交换次数，也初始化为 0；jiaohuan是一个布尔变量，用于标记每一轮冒泡排序过程中是否发生了元素交换。 - 外层
for循环控制排序的轮数，一共会进行n - 1轮排序（因为每一轮排序都会将当前未排序部分的最大元素 “浮” 到末尾，所以经过n - 1轮就可以完成整个数组的排序）。 - 内层
for循环用于在每一轮排序中比较相邻的元素。每次比较都会使cont变量加 1，以统计比较次数。当arr[j] > arr[j + 1]时，说明这两个相邻元素的顺序不对，需要交换它们的位置。此时会进行以下操作：- 将
jiaohuan变量设置为true，表示这一轮发生了交换。 - 使
jh_cont变量加 1，统计交换次数。 - 通过一个临时变量
temp来实现arr[j]和arr[j + 1]这两个相邻元素的交换。
- 将
- 在每一轮外层
for循环结束后，如果jiaohuan变量为false，即这一轮没有发生交换，说明数组已经有序，此时可以通过break语句提前结束整个冒泡排序过程，这是一种优化手段，可以提高排序效率，避免不必要的比较和交换操作。
2.5 排序后数组输出及统计信息输出
cout << "排序后的数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout<<"一共执行了"<<cont;
cout<<"一共交换了"<<jh_cont;
cout << endl;
- 同样使用循环遍历数组
arr，将排序后的数组元素依次输出到控制台，并在输出之前先输出提示信息 “排序后的数组：”。 - 接着通过
cout分别输出了在排序过程中一共执行的比较次数cont和一共进行的交换次数jh_cont，最后输出一个换行符endl，使控制台输出更加美观。
3. 关于冒泡排序算法特点
- 冒泡排序是一种简单的排序算法，它的基本思想是通过相邻元素的比较和交换，将最大（或最小）的元素逐步 “冒泡” 到数组的一端。
- 上述代码实现的升序排序，即每次比较相邻元素时，若前一个元素大于后一个元素，则交换它们的位置，经过多轮这样的操作，最终实现数组元素从小到大的排序。
- 冒泡排序的时间复杂度在最坏情况下为（当数组是逆序排列时），平均情况下也为，最好情况下（当数组已经有序时）时间复杂度为，因为只需要遍历一遍数组确认没有交换发生即可提前结束排序。
- 冒泡排序是一种稳定的排序算法，所谓稳定，就是在排序过程中，相等元素的相对顺序不会改变。在代码中可以看到，当相邻元素相等时，不会进行交换操作，从而保证了相等元素的相对顺序。
关于它的稳定性呢，其实取决于你判断两个数时用的是大于，小于，还是大于等于，小于等于。
这点决定了它的稳定性。举个例子，教室里按身高排座位。本来第一排第二排的学生身高一样。但似乎最后一排的学生身高最低，因此要把最后一排学生挪到第一排。稳定的情况是最后一排来第一排，第一二排统一后移。不稳定的情况可能会导致原来第一排的跑到了最后一排，跑到了第二排后面。
所以这些细节问题都是我们做算法需要考虑的问题。