ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【数据结构】排序算法---冒泡排序 [打印本页]

作者: 我爱普洱茶 时间: 昨天 07:46
标题: 【数据结构】排序算法---冒泡排序

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语言

#include <stdio.h>
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 <iostream>
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;
}

复制代码

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/142211564

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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)