题目描述
给定一个长度为 $n$ 的由小写字母构成的字符串。请你按照 $a∼z$ 的顺序,对字符串内的字符进行重新排序,并输出重新排序后的字符串。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $n$ 。
第二行包含一个长度为 $n$ 的由小写字母构成的字符串。
输出格式
每组数据输出占一行,输出重新排序后的字符串。
数据范围
前3个测试点满足 $1 ≤ T ≤ 5$,$1 ≤ n ≤ 10$。
所有测试点满足 $1 ≤ T ≤ 100$,$1 ≤ n ≤ 200$。
输入样例:
2
3
cba
3
acb
输出样例:
abc
abc
个人思路
采用了ASCII码对字符进行转换并排序,使用了快速排序的模板
$Tips$
本题采用不调用库函数的复杂写法,目的是为了熟悉快速排序模板的书写以及原理的巩固,同时熟悉C++语言中字符与其ASCII码之间的转换写法。
$C++$ 代码
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int T = 110, N = 210; // T:最大测试组数,N:每个测试组的最大长度
int t, n; // t:输入的测试组数,n:每个元素的长度
string arr[T]; // 字符串数组 存储排序后的字符串元素
char elem[N]; // 字符数组,元素
int elems[N]; // 用于存储测试组每个元素的ASCII码,用于元素的排序
// 快速排序模板
void quick_sort(int q[], int l, int r)
{
// 递归的终止情况
if (l >= r) return;
// 第一步:分成子问题
// 临界点为中点
int x = q[(l + r) >> 1], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if (i < j) swap(q[i], q[j]);
}
// 第二步:递归处理子问题
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
cin >> t; // 测试组数
// 遍历处理每个测试组
for(int i = 0; i < t; i++)
{
cin >> n; //每个字符数组的长度
for(int j = 0; j < n; j++)
{
cin >> elem[j];
elems[j] = static_cast<int>(elem[j]); // 将逐个字符转换为其对应的 ASCII 码,并将其存储到整数数组
}
elem[n] = '\0'; // 确保字符数组以 null 终止,以便转换为字符串
quick_sort(elems, 0, n-1); // 将 ASCII 码逐个进行快速排序
// 将排序好的ASCII码转换成字符并更新 elem 字符数组
for (int k = 0; k < n; k++)
{
elem[k] = static_cast<char>(elems[k]);
}
// 将字符数组 elem 转换为字符串
string strElem(elem);
// 将转换后的字符串追加到字符串数组 arr 后面
arr[i] = strElem; // 假设每组数据的字符串只需存储到 arr 的 i 个位置
}
// 打印结果
for(int i = 0; i < t; i++)
{
cout << arr[i] << "\n";
}
return 0;
}
$yxc’s cpp $
**调用了sort排序函数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
string s;
cin >> n >> s;
sort(s.begin(), s.end());
cout << s << endl;
}
return 0;
}