1、冒泡排序：冒泡排序是通过对相邻的数据元素进行交换，逐步将待排序序列排成有序序列的过程。 如以升序为例（假设存储结构为数组array[len]，长度为len）：在一趟冒泡排序中，从第一个记录开始，扫描整个待排序序列（注意是待排序序列，而不是整个记录序列，待排序序列随着排序的趟数的增加而减少，最后一趟待排序序列为2，只用交换两个元素），在一趟扫描中，最终必然将最大的元素排在待排序序列的末尾，这也是最大元素应该在的位置，第一躺时会将整个记录中最大元素排在最后一个位置array[len]。然后进行第二趟，重复上述过程，结果将次大记录放在第array[len-1]上，......重复上述过程，直至整个数组余下一个记录为止。若在某一趟的冒泡排序过程中，一个逆序也没找到，则可以直接结束整个排序过程，所以冒泡排序过程最多只进行len-1趟，冒泡排序也是唯一一个可以不用排序而直接终止排序的排序算法。冒泡排序的代码如下：(采用C++模板类)
#include<iostream>
using namespace std;
template<typename T>
void bubble( T t[],int len)//注意模板中的参数T为参数类型，所以不能写成T[]
{
bool flag=true;
int i,j;
for(i=1;i<=len-1&&flag;i++)
{
flag=false;
for(j=0;j<len-i;j++)//如果外层循环是从1开始，那么内层循环j<len-i,
//不能取等号，否则会产生下标越界，因为下面的交换判断语句为t[j]
//与t[j+1]，
{
if(t[j]>t[j+1])
{
swap(t[j],t[j+1]);
flag=true;
}
}
}
}
void main()
{
int a[]={4,2,1,3,5,7,6};
char x[100]={'x','y','s','a','n','c','m'};//此处必须指定数组的大小，虽然不指定也不会出错，但是当用字符去初始化一个没定义长度的字符数组时，系统不会默认在
//末尾添加'\0'，所以此时不能用strlen函数来求该字符数组的长度，而当指定数组的大小后，余下的系统自动赋值为空，即'\0'
// int len=strlen(a);错误，strlen函数的参数为char*类型
int len=sizeof(a)/4;
for(int i=0;i<len;i++)
cout<<a[i]<<' ';
cout<<endl;
cout<<"排序后结果为"<<endl;
bubble(a,len);
for(int i=0;i<len;i++)
cout<<a[i]<<' ';
cout<<endl;
int str_len=strlen(x);
for(int i=0;i<len;i++)
cout<<x[i]<<' ';
cout<<endl;
cout<<"排序后结果为"<<endl;
bubble(x,str_len);
for(int i=0;i<len;i++)
cout<<x[i]<<' ';
cout<<endl;
}
复杂度分析：冒泡排序最好的情况就是当待排序序列正序排列的时候，则只需要进行一趟排序，在排序过程中进行n-1次比较，而不需要移动记录，即外层for循环只需执行一次，此时复杂度为O(n).最坏的情况就是逆序排列的时候，则第i趟需要进行n-i次比较，3（n-i）次移动，即外层for循环与内层for循环都得执行，总的比较次数为n（n-1）/2，而移动次数为3n（n-1）/2，此时复杂度为O(n*n).
