【数据结构】排序算法---冒泡排序

  
1. 定义

冒泡排序（英语：Bubble sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比力两个元素，如果它们的序次错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
由于在算法的执行过程中，较小的元素像是气泡般渐渐「浮」到数列的顶端，故叫做冒泡排序。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证实该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
2. 算法步骤

这里以升序为例：

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

3. 动图演示

4. 性子

稳固性：
冒泡排序是一种稳固的排序算法。
空间复杂度：
冒泡排序的空间复杂度为                                   O                         (                         1                         )                              O(1)                  O(1)
时间复杂度：

• 在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为                                             O                               (                               n                               )                                      O(n)                        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语言

1. #include <stdio.h>
2. void bubble_sort(int arr[], int len) {
3.         int i, j, temp;
4.         for (i = 0; i < len - 1; i++)
5.                 for (j = 0; j < len - 1 - i; j++)
6.                         if (arr[j] > arr[j + 1]) {
7.                                 temp = arr[j];
8.                                 arr[j] = arr[j + 1];
9.                                 arr[j + 1] = temp;
10.                         }
11. }
12. int main() {
13.         int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
14.         int len = sizeof(arr) / sizeof(arr[0]);
15.         bubble_sort(arr, len);
16.         int i;
17.         for (i = 0; i < len; i++)
18.                 printf("%d ", arr[i]);
19.         return 0;
20. }

复制代码

Python

1. def bubbleSort(arr):
2.     for i in range(1, len(arr)):
3.         for j in range(0, len(arr)-i):
4.             if arr[j] > arr[j+1]:
5.                 arr[j], arr[j + 1] = arr[j + 1], arr[j]
6.     return arr

复制代码

Java

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

复制代码

C++

1. #include <iostream>
2. using namespace std;
3. template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
4. void bubble_sort(T arr[], int len) {
5.         int i, j;
6.         for (i = 0; i < len - 1; i++)
7.                 for (j = 0; j < len - 1 - i; j++)
8.                         if (arr[j] > arr[j + 1])
9.                                 swap(arr[j], arr[j + 1]);
10. }
11. int main() {
12.         int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
13.         int len = (int) sizeof(arr) / sizeof(*arr);
14.         bubble_sort(arr, len);
15.         for (int i = 0; i < len; i++)
16.                 cout << arr[i] << ' ';
17.         cout << endl;
18.         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 };
19.         len = (float) sizeof(arrf) / sizeof(*arrf);
20.         bubble_sort(arrf, len);
21.         for (int i = 0; i < len; i++)
22.                 cout << arrf[i] << ' '<<endl;
23.         return 0;
24. }

复制代码

Go

1. func bubbleSort(arr []int) []int {
2.         length := len(arr)
3.         for i := 0; i < length; i++ {
4.                 for j := 0; j < length-1-i; j++ {
5.                         if arr[j] > arr[j+1] {
6.                                 arr[j], arr[j+1] = arr[j+1], arr[j]
7.                         }
8.                 }
9.         }
10.         return arr
11. }

复制代码

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。
也可以点点关注，避免以后找不到我哦！
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/142211564
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。