算法思想：两两比较待排序的相邻记录，如果逆序，那么进行交换。采用两个循环嵌套语句，内层循环每次可以选出待排元素的最小值或最大值，外层循环每次排除掉一个内层循环选出的最值。
空间复杂度：O(1) —需要一个辅助空间 时间复杂度：O(n^2)–有两层循环
算法特点：稳定排序。可以采用链式结构，因为只有相邻元素的操作。缺点：N较大，记录无序时花费时间代价大。
#include <iostream> using namespace std; #include<stdio.h> //严蔚敏《数据结构》教材写法 /* int *bubble(int original[],int length) { int j; int m=length-1; int flag=1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(original[j+1]<original[j]) { flag=1; original[0]=original[j+1]; original[j+1]=original[j]; original[j]=original[0]; } --m; } return original; } */ //双for，更容易理解 int* bubble(int original[],int length) { int i,j;//循环变量 int flag=0;//标记变量，判断是否循环 for(i=length;i>1;i--) { for(j=1;j<i;j++)//两两记录比较大小，需要循环length-1次 { if(original[j+1]<original[j]) { original[0]=original[j+1]; original[j+1]=original[j]; original[j]=original[0]; flag=1;//只要有一次或者多次发生交换，flag置1 } } if(flag==0)//如果flag==0，相邻记录没有发生交换，表明数组已然有序 break;//那么退出循环，节约时间 } return original; } int main() { int *original; int paixu[100]={0}; original=new int[100]; int i,n; paixu[0]=0; for(i=1;i<100;i++) { scanf("%d",&paixu[i]); if(getchar()=='\n') break; else continue; } n=i; original=bubble(paixu,n); printf("排序后的结果：\n"); //输出排序后的数组 for(i=1;i<=n;i++) { printf("%d ",original[i]); } printf("\n"); delete []original; return 0; }说明：冒泡排序很简单，但是很基础。设立flag标志，减少计算机的无用计算，这种思想很重要。之后练习单链表时候，再使用链表存储结构将冒泡排序实现。。
