个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创排序算法(3)之冒泡排序
收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1.常见排序算法
2.冒泡排序
2.1冒泡排序的概念
2.2冒泡排序的示例
2.3冒泡排序的动图演示
2.4冒泡排序的代码展示
2.5冒泡排序的优化
2.6测试代码
2.6.1未经优化的冒泡排序
2.6.2经过优化的冒泡排序
2.7时间复杂度分析
3.总结
今天说的是常见排序算法中的冒泡排序,本来是想和快排放在一起的,但快排的内容实在太多了,所以只能它和快排分开来说,欢迎大家点赞👍 收藏✨ 留言✉ 加关注💓
1.常见排序算法
2.冒泡排序
2.1冒泡排序的概念
冒泡排序是一种基本的比较排序算法，其名称由其排序过程中较小或较大的元素像气泡一样从数组的一端“浮”到另一端而来。其基本思想是通过反复交换相邻的未按次序排列的元素，从而使较小（或较大）的元素逐步“浮”到数组的顶端，而较大（或较小）的元素则“沉”到数组的底端。
2.2冒泡排序的示例
假设有数组 [5, 3, 8, 4, 2]，使用冒泡排序的过程如下：
- 第一次排序：比较并交换 [5, 3] -> [3, 5], [5, 8] -> [5, 8], [8, 4] -> [4, 8], [8, 2] -> [2, 8]。此时最大的元素 8 已经位于数组的最后。
- 第二次排序：比较并交换 [3, 5] -> [3, 5], [5, 4] -> [4, 5], [5, 2] -> [2, 5]。此时第二大的元素 5 已经位于倒数第二位。
- 第三次排序：比较并交换 [3, 4] -> [3, 4], [4, 2] -> [2, 4]。此时第三大的元素 4 位于倒数第三位。
- 第四次排序：比较并交换 [3, 2] -> [2, 3]。此时第四大的元素 3 位于倒数第四位。
最终排序结果为 [2, 3, 4, 5, 8]。
2.3冒泡排序的动图演示
冒泡排序的步骤：
-
比较相邻元素：从数组的第一个元素开始，依次比较相邻的两个元素。
-
交换元素位置：如果发现第一个元素比第二个元素大（或小），则交换它们的位置，以使较小（或较大）的元素向前移动一位。
-
移动到下一对相邻元素：继续向数组的下一对相邻元素应用步骤 1 和步骤 2，直到数组末尾。此时，最后的元素会是数组中的最大（或最小）值。
-
重复以上步骤：重复以上步骤，每次减少未排序元素的数量，直到整个数组排序完成。
2.4冒泡排序的代码展示
注意:Swap函数是我已经实现了的函数,如果大家没有实现可以通过另一个变量来完成
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
swap(&a[i - 1], &a[i]);
}
}
}
}
Swap函数
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
2.5冒泡排序的优化
当某一趟排序未发生任何交换时，即可判断数组已经排好序，可以提前结束排序过程。这种优化在最佳情况下（数组已经有序）能够将时间复杂度降至 O(n)。
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
// 单趟
int flag = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}优化 (if (flag == 0) break;):在每一趟排序结束后，通过检查 flag 的值，如果 flag 仍为 0，表示数组已经是有序的，可以提前结束排序过程，避免不必要的比较。
2.6测试代码
--测试oj链接--912. 排序数组 - 力扣（LeetCode）
2.6.1未经优化的冒泡排序
代码:
void Swap(int* p1, int* p2)
{
int a = *p1;
*p1 = *p2;
*p2 = a;
}
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
}
}
}
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize;
int* array = (int*)malloc(sizeof(int)*(*returnSize));
for(int i = 0; i < numsSize; i++)
{
array[i] = nums[i];
}
BubbleSort(array, numsSize);
return array;
}结果只通过了10个例子
2.6.2经过优化的冒泡排序
代码
void Swap(int* n, int* m)
{
int p = *n;
*n = *m;
*m = p;
}
void BubbleSort(int* a, int n)
{
for(int j = 0; j < n; j++)
{
int flag = 0;
for(int i = 1; i < n - j; i++)
{
if(a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
flag = 1;
}
}
if(!flag) break;
}
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
(*returnSize) = numsSize;
int* array = (int*)malloc(sizeof(int)*(*returnSize));
for(int i = 0; i < numsSize; i++)
{
array[i] = nums[i];
}
BubbleSort(array, numsSize);
return array;
}结果也只通过了十个例子(有序序列很少见,优化后仍然大部分是O(N^2)
2.7时间复杂度分析
时间复杂度
冒泡排序的时间复杂度取决于比较和交换的次数。
最好情况时间复杂度： 当输入数组已经是按升序排列时，每一趟排序都不需要交换，只需进行 n-1 次比较。因此，最好情况时间复杂度为 O(n)。
最坏情况时间复杂度： 当输入数组按降序排列时，每一对相邻元素都需要交换，每趟排序需要进行 n-1 次交换操作和比较。因此，最坏情况时间复杂度为 O(n^2)。
平均情况时间复杂度： 平均情况下，冒泡排序的时间复杂度也是 O(n^2)。这是因为无论初始输入如何，都需要进行大致相同数量的比较和交换操作。
冒泡排序在最好情况下的优化是通过设置一个标志位（例如
flag）来检测是否进行了交换，如果某一趟排序中没有发生交换，则认为数组已经有序，可以提前结束排序过程，从而将最好情况的时间复杂度优化到 O(n)。空间复杂度
冒泡排序的空间复杂度是 O(1)，即它是一个原地排序算法。除了输入数组外，它只需要常数级别的额外空间来存储几个临时变量，如循环中的索引和交换时的临时变量。
3.总结
冒泡排序的时间复杂度主要由比较和交换操作决定，最好情况下可以达到 O(n)，最坏和平均情况下为 O(n^2)。其空间复杂度为 O(1)，在空间使用上非常高效。尽管冒泡排序在大规模数据上不如快速排序、归并排序等更高效的排序算法，但它的实现简单直观，适用于小型数据集或者作为教学和理解排序算法的基础。
快速排序已经在加更中,欢迎 点赞👍 收藏✨ 留言✉ 加关注💓
