Simone数据结构冒泡排序详解
的有关信息介绍如下：
对于计算机专业的大学生而言，冒泡排序应该是大学里第一个接触的排序类算法，但是很多同学刚接触时不大明白，自己针对自己的理解用比价浅显的语言来讲解一下冒泡排序让大家能够很容易学懂。
冒泡排序：冒泡排序是通过对相邻的数据元素进行交换，逐步将待排序序列排成有序序列的过程。 如以升序为例（假设存储结构为数组array[len]，长度为len）：在一趟冒泡排序中，从第一个记录开始，扫描整个待排序序列（注意是待排序序列，而不是整个记录序列，待陕薪排序序列随着排序的趟数的增加而减少，最后一趟待排序序列为2，只薪边沫用交换两个元素），在一趟扫描中，最终必然将最大的元素排在待排序序列的末尾，这也是最大元素应该在的位置，第一躺时会将整个记录中最大元素排在最后一个位置array[len]。然后进行第二趟，重复上述过程，结果将次大记录放在第array[len-1]上，......重复上述过程，直至整个数组余下一个三之记录为止。若在某一趟的冒泡排序过程中，一个逆序也没找到，则可以直接结束整个排序过程，所以冒泡排序过程最多只进行len-1趟，冒泡排序也是唯一一个可以不用排序而直接终止排序的排序算法。冒泡排序的代码如下：(采用C++模板类)
#include
using namespace std;
template
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 //不能取等号，否则会产生下标越界，因为下面的交换判断语句为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={'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 cout< cout< cout<<"排序后结果为"< bubble(a,len); for(int i=0;i cout< cout< int str_len=strlen(x); for(int i=0;i cout< cout< cout<<"排序后结果为"< bubble(x,str_len); for(int i=0;i cout< cout< } 复杂度分析：冒泡排序最好的情况就是当待排序序列正序排列的时候，则只需要进行一趟排序，在排序过程中进行n-1次比较，而不需要移动记录，即外层for循环只需执行一次，此时复杂度为O(n).最坏的情况就是逆序排列的时候，则第i趟需要进行n-i次比较，3（n-i）次移动，即外层for循环与内层for循环都得执行，总的比较次数为n（n-1）/2，而移动次数为3n（n-1）/2，此时复杂度为O(n*n).
