冒泡排序
1.1 原理
- 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
- 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
- 属于交换排序有：冒泡排序和快速排序
冒泡排序是一种简单的排序算法
冒泡排序：基于数组（顺序表）的结构进行排序
原理：
- 它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来
- 重复地进行直到没有再需要交换，也就是说该数列已经排序完成
具体步骤如下：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
原始数组如下，使用冒泡排序进行排序（升序）
第一趟：对0-n-1个元素进行遍历，依次对比前后的大小，若是不满足前小后大就交换，此时最大的数就被挪到了最后一个位置（10个元素比较了9次）
第二趟：对0-n-2个元素进行遍历，依次对比前后的大小，若是不满足前小后大就交换，此时最大的数就被挪到了倒数第二个位置。
由于9已经判断为最大值，所以第二次冒泡排序时就需要找出除9之外的无序表中的最大值，比较过程和第一趟排序完全相同（9个元素比较了8次，除掉9）
重复上述动作，每一次都将最大的数向后移动，直到遍数组有序
1.2 代码实现（C/C++）
代码实现如下：（升序）
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
//每一趟冒泡的过程
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]); // 交换
}
}
}
}
观察发现当数组已经有序了（假设是升序），如[1，2，3，4，5，6，7，8]，上面的代码依旧继续进行下一轮的比较，直到所有的数进行比较、排序完，很明显后面的比较没有意义的这就会让这些代码的效率降低
在这种情况下，我们就不必要对有序的数进行排序，以此减少代码执行的次数，提高代码的效率。
因此，可以设置一个exchange ，如果已经排好序了就令 exchange == 0结束循环；如果不是有序的就令exchange == 1继续执行
代码如下：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* arr, int n)
{
assert(arr);
for (int i = 0; i < n - 1; i++)
{
int exchange = 0;// 记录该趟猫爬排序是否进行交换
// 每一趟冒泡的过程
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]); // 交换
exchange = 1; // 发生数据交换，置exchange为1
}
}
if (exchange == 0) // 该趟冒泡排序没有进行交换，已有序，跳出循环
{
break;
}
}
}
1.3 特性总结
- 时间复杂度：
O(N^2) - 空间复杂度：
O(1) - 稳定性：稳定
- 适用范围：冒泡排序适用于小型的数据集，对于大型数据集效率较低
--------------------- END ----------------------
「 作者 」 枫叶先生
「 更新 」 2024.1.20
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
或有谬误或不准确之处，敬请读者批评指正。