7-1 字符串的冒泡排序

冒泡排序：依次比较相邻的两个数，时间复杂度O（n²），相同元素的前后顺序不会改变，是一种稳定的排序算法。

时间复杂度受数据的原始状态影响：

最好情况-正序：1趟排序，比较关键字n-1次，移动0次，O（n）

最坏情况-反序：n-1趟排序，每趟比较n-i次关键字（1<<i<<n-1），每次比较都要做3次记录，O（n²）

如序列：b、c、e、a、f、d

第一趟 （b c) e a f d ==> b (c e) a f d ==> b c (a e) f d ==> b c a (e f) d ==> b c a e (d f)

第一趟结果：b c a e d f

第二趟 （b c) a e d f ==> b (a c) e d f ==> b a (c e) d f ==> b a c (d e) f ==> b a c d (e f) 

第二趟结果：b a c d e f

第三趟 （a b) c d e f ==> a b c d e f  不需要再交换，排序结束

7-1 字符串的冒泡排序

输入格式：

输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。

输出格式：

输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。

输入样例：

6 2
best
cat
east
a
free
day

输出样例：

best
a
cat
day
east
free

#include <bits/stdc++.h>
//万能头文件
//2019/07/17
using namespace std;
int main()
{
int n,k;
//n个字符串，扫描k遍
int i,j;
string str[100],temp;
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
cin>>str[i];
//输入字符串
for(i=0;i<k;i++)
//记录扫描趟数
{
for(j=0;j<n-1;j++)
//n-1！！！
if(str[j]>str[j+1]) //string比较大小直接用运算符，每次当前关键字和后面的作比较
{
temp=str[j];
//交换值记录三次
str[j]=str[j+1];
str[j+1]=temp;
}
}
for(i=0;i<n;i++)
cout<<str[i]<<endl;
return 0;
}

最后

以上就是糟糕丝袜为你收集整理的7-1 字符串的冒泡排序的全部内容，希望文章能够帮你解决7-1 字符串的冒泡排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。