C++常见排序算法——冒泡排序算法

首先说一下冒泡排序的基本算法思想：

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

以从小到大排序为例：a[5]={3,5,4,1,0};

1. 先将3和5进行比较，已经是我们需要的正序，不需要交换位置；
2. 再将5和4进行比较，不是正序，相互交换顺序，序列变为{3,4,5,1,0}。
3. 再将5和1进行比较，不是正序，相互交换顺序，序列变为{3,4,1,5,0}。
4. 再将5和0进行比较，不是正序，相互交换顺序，序列变为{3,4,1,0,5}。

至此，第1轮冒泡就已经完成了，最大值5到了序列的最后面。

由于5的位置已经排好序，所以第2轮，5不再参与排序，将{3,4,1,0}置为有序序列即可。

假设数组元素个数为n，从上面第1轮的比较来看，我们可以得出如下结论：

1. 我们将冒泡排序的轮数设为 i ，每完成1轮冒泡排序，就会增加一个元素处于有序状态，所以在 (n-1) 轮排序结束后，就会有 n-1 个元素处于有序状态，而剩下的最后一个元素，自然是最小（大）值，不用再进行排序，所以，冒泡排序比较的轮数为 (n-1) 。
2. 我们将每轮需要比较的次数设为 j ，第1轮( i 值为0)需要比较的次数为4，从 {3,4,1,0} 中不难看出，第2轮( i 值为1)需要比较的次数为3次，说明每轮比较的次数 j 与冒泡的轮数  i  值有关，且 j = n-i-1。

确定好上面两条结论以后，我们开始用代码实现冒泡排序算法：

#include <iostream>
using namespace std;
//对a[]进行正序(从小到大)排序
void bubblesort(int *a,int len)	//形参a取到实参a传递过来的数组首地址
                                //然后解引用，取到数组的值 
{
	for (int i=0;i<len-1;i++)	//i控制排序的轮数 
	{
		for (int j=0;j<len-i-1;j++)	//j控制每轮需要比较的次数 
		{
			if(a[j+1]<a[j])	//不满足正序要求，交换顺序 
			{
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}	
}
 
int main()
{
	int a[10]={2,6,3,8,5,1,0,7,9,4};
	int len = sizeof(a)/sizeof(int);	//	计算数组元素个数 
	bubblesort(a,len);	//a为数组a[10]首地址，作为实参传递给形参 
	for(int i=0;i<len;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

得到正序排列的值： 0 1 2 3 4 5 6 7 8 9。