排序算法(3)之冒泡排序
个人主页：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 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 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 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结果只通过了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 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结果也只通过了十个例子(有序序列很少见,优化后仍然大部分是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)，在空间使用上非常高效。尽管冒泡排序在大规模数据上不如快速排序、归并排序等更高效的排序算法，但它的实现简单直观，适用于小型数据集或者作为教学和理解排序算法的基础。
快速排序已经在加更中,欢迎 点赞👍 收藏✨ 留言✉ 加关注💓
-
