冒泡排序

冒泡排序

冒泡排序（BubbleSort），是比较简单的一个排序算法。它重复的走访数组里的元素，一次比较两个元素，如果符合交换规则就进行交换，否则就不进行。一直循环，直到没有要交换的元素为止。

原理

  • 从左到右遍历，比较相邻的两个元素，较大或者较小的元素会被放在
  • 较大或者较小的元素会被放在右边
  • 重复上述步骤，直到所有元素都按照顺序排列

实践

假设我们有个数组，我们想让它从小到大排序

1
a[5]={7,2,5,0,9}

从小到大排序，也就是大元素向后移动，最大的就像海里的气泡一样，向海面（数组的最后）上冒，

第一次循环：

也就是i=0时，前两个元素7和2，7比2大，就交换它们的位置。这时候数组变成

1
a={2,7,5,0,9}

第二次循环：

i=1，7和5比，符合规则，交换

1
a={2,5,7,0,9}

第三次循环：

i=2，7和0比，符合规则，交换

1
a={2,5,0,7,9}

当下一循环时，7和9比，不交换，至此第一次的排序已经完成，但是7前面的2，5，0还没排序，所以还要再来n（元素个数）次的外层循环。

代码实现

1
2
3
4
5
6
7
void swap(int &a,int &b){
	int temp;
	temp = a;
  a = b;
	b = temp;

}
1
2
3
4
5
6
for(int i=0;i<n-1;i++){ //n为数组的长度
	for(int j=0;j<n-i-1){
		if(a[j+1]>a[j]
			swap(a[j+1],a[j]);
	}
}