【数据结构】排序算法---冒泡排序（动图演示）_冒泡排序动图

文章目录

• 1. 定义
• 2. 算法步骤
• 3. 动图演示
• 4. 性质
• 5. 算法分析
• 6. 代码实现
• • C语言
  • Python
  • Java
  • C++
  • Go
• 结语

1. 定义

冒泡排序（英语：Bubble sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

2. 算法步骤

这里以升序为例：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

3. 动图演示

4. 性质

稳定性：

冒泡排序是一种稳定的排序算法。

空间复杂度：

冒泡排序的空间复杂度为$O(1)$

时间复杂度：

• 在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为$O(n)$。

• 在最坏情况下，冒泡排序要执行 ( n − 1 ) n 2(n-1)n \\over 2 2(n−1)n​次交换操作，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

• 冒泡排序的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

5. 算法分析

这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

6. 代码实现

C语言

#include void bubble_sort(int arr[], int len) { int i, j, temp; for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; }}int main() { int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 }; int len = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, len); int i; for (i = 0; i < len; i++) printf(\"%d \", arr[i]); return 0;}

Python

def bubbleSort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i): if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr

Java

public class BubbleSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) {  int tmp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = tmp;  flag = false; } } if (flag) { break; } } return arr; }}

C++

#include using namespace std;template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符void bubble_sort(T arr[], int len) { int i, j; for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);}int main() { int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 }; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << \' \'; cout << endl; float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; len = (float) sizeof(arrf) / sizeof(*arrf); bubble_sort(arrf, len); for (int i = 0; i < len; i++) cout << arrf[i] << \' \'<<endl; return 0;}

Go

func bubbleSort(arr []int) []int { length := len(arr) for i := 0; i < length; i++ { for j := 0; j < length-1-i; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] } } } return arr}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
桶排序：https://blog.csdn.net/2301_80191662/article/details/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564