1.什么是冒泡排序算法？
将一组元素两两相比较，直至该组元素顺序为由小到大。
2.冒泡排序算法原理：
（1）从首位开始，比较相邻的元素，如果第一个元素大于第二个元素，就交换两者位置，直至结尾的最后一对。
（2）经过（1）的动作，此刻参与比较的元素中最大的一个排在了末尾。
（3）将上述动作中最后一位元素之前的元素再次进行（1）（2）步骤，当没有一对元素再需要排序就结束（1）（2）（3）步骤。
3.简单的事例：
首先定义一个数组：int a[6]={3,6,5,2,8,4};
按照冒泡排序的原理:
第一趟排序：
int exam;
if(a[0]>a[1]){
exam=a[0];
a[0]=a[1];
a[1]=exam;}//第一位和第二位排序；
if(a[1]>a[2]){
exam=a[1];
a[1]=a[2];
a[2]=exam;}//第二位和第三位排序；
if(a[2]>a[3]){
exam=a[2];
a[2]=a[3];
a[3]=exam;}//第三位和第四位排序；
if(a[3]>a[4]){
exam=a[3];
a[3]=a[4];
a[4]=exam;}//第四位和第五位排序；
if(a[4]>a[5]){
exam=a[4];
a[4]=a[5];
a[5]=exam;}//第五位和第六位排序；
结果：六个元素比了五次，数组结果a[6]={3,5,2,6,4,8};
第二趟排序：第一次排序的最大值不再参与，此刻五个元素进行比较。
int exam;
if(a[0]>a[1]){
exam=a[0];
a[0]=a[1];
a[1]=exam;}//第一位和第二位排序；
if(a[1]>a[2]){
exam=a[1];
a[1]=a[2];
a[2]=exam;}//第二位和第三位排序；
if(a[2]>a[3]){
exam=a[2];
a[2]=a[3];
a[3]=exam;}//第三位和第四位排序；
if(a[3]>a[4]){
exam=a[3];
a[3]=a[4];
a[4]=exam;}//第四位和第五位排序；
结果：五个元素比了四次，数组a[6]={3,2,5,4,6,8};
同理可知接下来还需要3趟排序，所以当假设数组元素有n个时，需要(n-1)趟排序，第i趟排序中元素两两比较的次数为(n-i),(i>=1)。
4.核心代码：
（1）双重循环实现即：
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)//第i趟排序需要两两比较的次数。
{
if(a[j]>a[j+1])
{
exam=a[j];
a[j]=a[j+1];
a[j+1]=exam;
}
}
}
（2）递归实现即：
void sort(int i,int n,int a[]){ //i初值为0，n代表元素的个数
if(i==(n-1)){
for(int o=0;o<n;o++);
cout<<a[o]<<" ";}
else
{
for(int j=0 ;j<n-1;j++){
if(a[j]>a[j+1]){
exam=a[j];
a[j]=a[j+1];
a[j+1]=exam;
}
}
}
sort(i,n-1,a);
}
5.优化算法
假设数组a[6]={7,2,3,4,5,6};
第一趟排序后将最大数据排到了最后；
第二趟排序的时候会发现没有出现相邻两数据交换的情况，接下来第三趟至第五趟都没出现；
所以由此可得出，当某趟排序不会发生两两数据进行交换时，该组数据的排序结束。
优化算法如下:
bool t=false;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
f=false;
if(a[j]>a[j+1])
{
exam=a[j];
a[j]=a[j+1];
a[j+1]=exam;
f=true;
}
}
if(f==false)break;
}
6.应用
题目：设有n个正整数，将他们连接成一排，组成一个最大的多位整数。
如:n=3时，3个整数13,312,343,连成的最大整数为34331213。
如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。
输入描述:
有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。
输出描述:
每组数据输出一个表示最大的整数。
解答：
# include <iostream>
# include <vector>
using namespace std;
int main(){
vector <string> array;
int n;
cin>>n;
for (int i=0;i<n;i++){
string num;
cin>>num;
array.push_back(num);
}
for(int m=0;m<n-1;m++){
int g=0;
for(int j=0;j<n-m-1;j++){
string x;
x=array[j];
string s1,s2;
s1=array[j]+array[j+1];
s2=array[j+1]+array[j];
if(s1<s2){
array[j]=array[j+1];
array[j+1]=x;
g=1;
}
}
if(g==0)break;
}
for(int y=0;y<n;y++){
cout<<array[y];
}
return 0;
} 
网友评论