PTA基础编程题目集 7-30字符串的冒泡排序（C++语言实现）

摘要：本文是PTA编程题"字符串的冒泡排序"的题解，涵盖题目描述、输入输出格式及C++语言实现，展示基于strcmp比较字符串字典序进行冒泡排序K趟后输出中间结果的方法。

题目描述

我们已经知道了将N个整数按从小到大排序的冒泡排序法。本题要求将此方法用于字符串序列，并对任意给定的K（<N），输出扫描完第K遍后的中间结果序列。

输入格式：

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

输出格式：

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

输入样例：

6 2 best cat east a free day

输出样例：

best a cat day east free

解题思路

核心问题分析：将冒泡排序算法扩展到字符串序列，按字典序升序排列字符串，执行K趟排序后输出中间结果。关键点在于使用strcmp函数比较字符串字典序，使用strcpy函数交换字符串内容。

算法原理说明：使用二维字符数组存储N个字符串，外层循环控制K趟排序，内层循环逐对比较相邻字符串。strcmp(a,b)>0表示a的字典序大于b时需要交换位置。交换时通过临时字符数组和strcpy函数完成两个字符串的整体拷贝交换。第i趟排序后，末尾i个字符串已有序。

具体计算步骤：

1. 读入N（字符串数）和K（排序趟数）
2. 逐行读入N个字符串存入二维数组strs
3. 外层i从0到K-1执行K趟冒泡排序
4. 第i趟内层j从0到n-2-i，用strcmp比较strs[j]和strs[j+1]，若前者字典序大则用strcpy交换
5. K趟排序后逐行输出数组中的所有字符串

代码部分实现

#include<iostream>#include<cstring>usingnamespacestd;intmain(){intn,k;cin>>n>>k;charstrs[100][11];for(inti=0;i<n;i++){cin>>strs[i];}for(inti=0;i<k;i++){for(intj=0;j<n-1-i;j++){if(strcmp(strs[j],strs[j+1])>0){chartemp[11];strcpy(temp,strs[j]);strcpy(strs[j],strs[j+1]);strcpy(strs[j+1],temp);}}}for(inti=0;i<n;i++){cout<<strs[i]<<endl;}return0;}

代码流程说明

1. 输入数据：读入n和k，然后逐行读入n个字符串存入二维字符数组strs（每行最多10字符+结束符共11字节）
2. K趟冒泡排序：外层i从0到k-1，共k趟；内层j从0到n-2-i，用strcmp比较相邻两个字符串字典序
3. 字符串交换：若strcmp返回值>0表示前串大于后串需交换，通过临时数组temp配合strcpy完成两个字符串的内容拷贝交换
4. 输出结果：遍历二维数组，每行输出一个字符串，即K趟排序后的中间结果

代码流程图

解题流程图