冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地遍历待排序的列表,比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像"气泡"一样逐渐"浮"到列表的顶端。
1. 算法步骤
比较相邻元素:从列表的第一个元素开始,比较相邻的两个元素。
交换位置:如果前一个元素比后一个元素大,则交换它们的位置。
重复遍历:对列表中的每一对相邻元素重复上述步骤,直到列表的末尾。这样,最大的元素会被"冒泡"到列表的最后。
缩小范围:忽略已经排序好的最后一个元素,重复上述步骤,直到整个列表排序完成。
2. 动图演示
假设有一个待排序的列表 [5, 3, 8, 4, 6],冒泡排序的过程如下:
第一轮遍历:
比较 5 和 3,交换位置,列表变为
[3, 5, 8, 4, 6]
。比较 5 和 8,不交换。
比较 8 和 4,交换位置,列表变为
[3, 5, 4, 8, 6]
。比较 8 和 6,交换位置,列表变为
[3, 5, 4, 6, 8]
。第一轮结束后,最大的元素 8 已经"冒泡"到列表的最后。
第二轮遍历:
比较 3 和 5,不交换。
比较 5 和 4,交换位置,列表变为
[3, 4, 5, 6, 8]
。比较 5 和 6,不交换。
第二轮结束后,第二大的元素 6 已经"冒泡"到列表的倒数第二位置。
第三轮遍历:
比较 3 和 4,不交换。
比较 4 和 5,不交换。
第三轮结束后,列表已经有序。
第四轮遍历:
比较 3 和 4,不交换。
列表已经完全有序。
实例
n = len(arr)
for i in range(n):
# 标记是否发生了交换
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
# 交换位置
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# 如果没有发生交换,说明列表已经有序,提前退出
if not swapped:
break
return arr
# 示例
arr = [5, 3, 8, 4, 6]
sorted_arr = bubble_sort(arr)
print(sorted_arr) # 输出: [3, 4, 5, 6, 8]
3. 时间复杂度
-
最坏情况:O(n²),当列表是逆序时。
-
最好情况:O(n),当列表已经有序时。
-
平均情况:O(n²)。
4. 空间复杂度
-
O(1),因为冒泡排序是原地排序算法,不需要额外的存储空间。
5. 优缺点
-
优点:
-
实现简单,代码易于理解。
-
原地排序,不需要额外的存储空间。
-
-
缺点:
-
效率较低,尤其是对于大规模数据集。
-
不适合处理几乎已经有序的列表,因为仍然需要进行多次遍历。
-
6. 什么时候最快
当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。
7. 什么时候最慢
当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。
8. JavaScript 代码实现
实例
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
9. Python 代码实现
实例
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
10. Go 代码实现
实例
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
}
11. Java 代码实现
实例
@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;
}
}
12. PHP 代码实现
实例
{
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
for ($j = 0; $j < $len - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j+1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
return $arr;
}
13. C 语言
实例
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;
}
14. C++ 语言
实例
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;
}
15. C#
实例
int temp = 0;
bool swapped;
for (int i = 0; i < intArray.Length; i++)
{
swapped = false;
for (int j = 0; j < intArray.Length - 1 - i; j++)
if (intArray[j] > intArray[j + 1])
{
temp = intArray[j];
intArray[j] = intArray[j + 1];
intArray[j + 1] = temp;
if (!swapped)
swapped = true;
}
if (!swapped)
return;
}
}
16. Ruby
实例
def bubble_sort!
for i in 0...(size - 1)
for j in 0...(size - i - 1)
self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1]
end
end
self
end
end
puts [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!
17. Swift
实例
func bubbleSort (arr: inout [Int]) {
for i in 0..<arr.count - 1 {
for j in 0..<arr.count - 1 - i {
if arr[j] > arr[j+1] {
arr.swapAt(j, j+1)
}
}
}
}
// 测试调用
func testSort () {
// 生成随机数数组进行排序操作
var list:[Int] = []
for _ in 0...99 {
list.append(Int(arc4random_uniform(100)))
}
print("\(list)")
bubbleSort(arr:&list)
print("\(list)")
}
原文地址:https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md
参考地址:https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
rookie
esh***fb@gmail.com
改进版冒泡排序
Python 实现:
Go 实现:
rookie
esh***fb@gmail.com
muen
zha***uen2011@163.com
啦~~~只是多了一个哪里已经有序的下表而已呀~~~性能提升了不少呢~~~
再来开个多线程~~~顺便加个条件才开多线程~~~性能提升的不是一点点呢~~~
muen
zha***uen2011@163.com
kezhuoquan
kez***quan@163.com
rust 版本的实现:
kezhuoquan
kez***quan@163.com