排序算法(一)--冒泡排序

冒泡排序

  冒泡排序是一种简单的排序算法
  重复的遍历要排序的数组,每次比较两个相邻的元素,符合给定的条件则交换两个元素,重复的遍历直到没有相邻的元素需要交换

时间复杂度

  • 最好的情况:O(n)
  • 最坏的情况:O(n2)
  • 平均:O(n2)

空间复杂度

  • 空间复杂度:O(1)

算法描述

冒泡排序是通过遍历比较相邻的两个元素来实现的
以下数字排序
2,3,4,1

第一轮第一次
2和3进行比较,因为2不大于3,所以不交换
2,3,4,1

第一轮第二次
3和4进行比较,因为3不大于4,所以不交换
2,3,4,1

第一轮第三次
4和1进行比较,因为4大于1,所以交换
2,3,1,4

第二轮第一次
2和3进行比较,因为2不大于3,所以不交换
2,3,1,4

第二轮第二次
3和1进行比较,因为3大于1,所以交换
2,1,3,4

第三轮第一次
2和1进行比较,因为2大于1,所以交换
1,2,3,4
到这里就排序完成了
还可以看看下面的动画演示

假如有以下数字需要排序

下标 0 1 2 3 4 5 6 7 8 9
元素 2 3 1 4 2 6 7 9 1 5

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
int arr[]={2,3,1,4,2,6,7,9,1,5};
int len=10;
for(int i=0;i<len-1;i++){
for(int j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
// 如果j的值大于j下一个的值就交换
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
int[] arr=new int[]{2,3,1,4,2,6,7,9,1,5};
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
// 如果j的值大于j下一个的值就交换
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
var arr=[2,3,1,4,2,6,7,9,1,5];
for(var i=0;i<arr.length-1;i++){
for(var j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
// 如果j的值大于j下一个的值就交换
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
1
2
3
4
5
6
7
8
arr=[2,3,1,4,2,6,7,9,1,5]
for i in range(len(arr)-1):
for j in range(len(arr)-1-i):
if arr[j]>arr[j+1]:
# 如果j的值大于j下一个的值就交换
temp=arr[j]
arr[j]=arr[j+1]
arr[j+1]=temp