数据结构课设个人（四）：冒泡排序

对于顺序存储的线性表，使用vector或数组，实现冒泡排序算法，并输出每趟的排序结果。

参考函数原型：（vector版本）

//冒泡排序

template

void BubbleSort( vector &A );

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）

第二行：待排序顺序表A的数据元素（数据元素之间以空格分隔）

如第一行输入值为0、1、2、3之外的值，直接输出“err”

否则：

第一行：第一趟的排序结果（数据元素之间以","分隔）

第二行：第二趟的排序结果（数据元素之间以","分隔）

...

第n行：最终的排序结果（数据元素之间以","分隔）

1
21.1 25.2 49.3 25.4 16.5 8.6

21.1,25.2,25.4,16.5,8.6,49.3
21.1,25.2,16.5,8.6,25.4,49.3
21.1,16.5,8.6,25.2,25.4,49.3
16.5,8.6,21.1,25.2,25.4,49.3
8.6,16.5,21.1,25.2,25.4,49.3

基本思想：水底下的气泡一样逐渐向上冒，每趟不断将记录两两比较，并按前小后大(或前大后小)规则交换。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。（设置flag标识交换是否发生）
前提：顺序存储结构

时间效率：O(n²) 
空间效率：O(1)  
稳定性： 稳定 

1.每次排完序最后的数一定是最大的，下一次不用在比较已经排好的部分了
2. 选择大数后移的冒泡，则内层循环的j每次从前往后走到i，而外层循环的i从后往前走！如果i和j的循环都是从前往后逐个增加，那么虽然大数能后移，但是例如最小的数还没到A[0]时，后续i增大已经不会再和A[0]位置比较互换了。（选择小数前移同理）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include    //用于ostringstream、istringstream、stringstream这三个类
#include
#include
#include
#define ArraySize 100
using namespace std;
template
void createvector( vector &A )
{
    ElemType tmp;
    string temp;
    getline(cin,temp);
    stringstream input(temp); //输入流
    while(input>>tmp)
        A.push_back(tmp);
}
//冒泡排序
template
void BubbleSort( vector &A ){
    ElemType temp=A[0];
    int length=A.size();
    if(length==1){   //别忘了length等于1的情况下要单独考虑！else语句中不包含该情况不会有输出
        cout<=1;i--){
                    int flag=1;   //用来标记是否该次排序有移动元素，如果没有说明序列已经有序，可以直接退出不必继续进行。
                    for(int j=0;jA[j+1]){
                        flag=0;
                        temp=A[j];
                        A[j]=A[j+1];
                        A[j+1]=temp;
                    }
            if(flag)  break;
                       for(int k=0;kkd;
    cin.ignore();
    if(kd==0){
        vector A;
        createvector( A );
        int t;
        BubbleSort( A );
    }
    else if(kd==1){
        vectorA;
        createvector( A );
     BubbleSort( A );
    }
    else if(kd==2){
         vectorA;
         createvector( A );
     BubbleSort( A );
    }
     else if(kd==3){
        vectorA;
        createvector( A );
     BubbleSort( A );
     }
    else
        cout<<"err"<