问题描述 :
对于顺序存储的线性表，使用vector或数组，实现冒泡排序算法，并输出每趟的排序结果。
参考函数原型：（vector版本）
//冒泡排序
template<class ElemType>
void BubbleSort( vector<ElemType> &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(n2)?
空间效率：O(1) ?
稳定性： 稳定?
举例：
注意事项：
1.每次排完序最后的数一定是最大的，下一次不用在比较已经排好的部分了
2.?选择大数后移的冒泡，则内层循环的j每次从前往后走到i，而外层循环的i从后往前走！如果i和j的循环都是从前往后逐个增加，那么虽然大数能后移，但是例如最小的数还没到A[0]时，后续i增大已经不会再和A[0]位置比较互换了。（选择小数前移同理）
代码实现：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <vector>
#include <sstream> //用于ostringstream、istringstream、stringstream这三个类
#include<stack>
#include<vector>
#include<queue>
#define ArraySize 100
using namespace std;
template<class ElemType>
void createvector( vector<ElemType> &A )
{
ElemType tmp;
string temp;
getline(cin,temp);
stringstream input(temp); //输入流
while(input>>tmp)
A.push_back(tmp);
}
//冒泡排序
template<class ElemType>
void BubbleSort( vector<ElemType> &A ){
ElemType temp=A[0];
int length=A.size();
if(length==1){ //别忘了length等于1的情况下要单独考虑！else语句中不包含该情况不会有输出
cout<<A[0]<<endl;
}
else{
for(int i=length-1;i>=1;i--){
int flag=1; //用来标记是否该次排序有移动元素，如果没有说明序列已经有序，可以直接退出不必继续进行。
for(int j=0;j<i;j++)//每次排完序最后的数一定是最大的，下一次不用在比较已经排好的了 j<i而非j<length-1
//！！！冒泡排序想后移大数，则i从后往前！j从前往后。如果i也是从前往后，那么虽然大数能后移，但是例如最小的数还没到A[0]时，后续i增大已经不会再和A[0]位置比较互换了
if(A[j]>A[j+1]){
flag=0;
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
if(flag) break;
for(int k=0;k<length-1;k++){
cout<<A[k]<<',';
}
cout<<A[length-1]<<endl;
}
}
}
int main()
{
int kd;
cin>>kd;
cin.ignore();
if(kd==0){
vector<int> A;
createvector( A );
int t;
BubbleSort( A );
}
else if(kd==1){
vector<double>A;
createvector( A );
BubbleSort( A );
}
else if(kd==2){
vector<char>A;
createvector( A );
BubbleSort( A );
}
else if(kd==3){
vector<string >A;
createvector( A );
BubbleSort( A );
}
else
cout<<"err"<<endl;
return 0;
}
?
?