问题描述小明在整理班级的图书角时发现每本书的封面上都印有一个字符可能是字母、数字或符号。为了便于分类老师希望将这些字符按照类型重新排序先排列所有数字字符0-9然后是所有字母字符a-z, A-Z最后是其他符号字符。同时要求在同类型字符中保持它们在原始字符串中的相对顺序不变。请帮助小明设计一个算法实现字符串的字符类型排序。要求算法的时间复杂度应为 O(n)其中 n 是字符串的长度。尽量减少额外空间的使用以体现算法优化能力。测试样例样例1输入s a1b2c3输出123abc解释原始字符串中的数字字符 1,2,3 排在前面接着是字母字符 a,b,c它们都保持了原始顺序。样例2输入s Hi! How are you? 123?输出123HiHowareyou! ? ?解释数字字符 1,2,3 先输出然后是大写字母 H,H小写字母 i,o,w,a,r,e,y,o,u最后是符号字符 !, 空格、?, 空格、?。所有字符保持原始相对顺序。样例3输入s Test123!!输出123Test!!解释数字字符 1,2,3 排在最前然后是字母字符 T,e,s,t最后是符号字符 !,!。约束条件1 ≤ s.length ≤ 1000字符串 s 可能包含任意可打印 ASCII 字符ASCII 值从 32 到 126输出字符串应包含输入字符串中的所有字符包括空格等符号且同类型字符的相对顺序与输入一致程序代码#include stdio.h#include string.h#include stdlib.hchar* sortCharacters(char* s) {int n strlen(s);char* result (char*)malloc((n 1) * sizeof(char));int idx 0;// 第一趟数字for (int i 0; i n; i) {if (s[i] 0 s[i] 9) {result[idx] s[i];}}// 第二趟字母for (int i 0; i n; i) {if ((s[i] a s[i] z) || (s[i] A s[i] Z)) {result[idx] s[i];}}// 第三趟其他符号for (int i 0; i n; i) {if (!(s[i] 0 s[i] 9) !(s[i] a s[i] z) !(s[i] A s[i] Z)) {result[idx] s[i];}}result[idx] \0;return result;}int main() {char* r1 sortCharacters(a1b2c3);char* r2 sortCharacters(Hi! How are you? 123?);char* r3 sortCharacters(Test123!!);printf(%s\n, r1); // 123abcprintf(%s\n, r2); // 123HiHowareyou! ? ?printf(%s\n, r3); // 123Test!!free(r1);free(r2);free(r3);return 0;}#include stdio.h #include string.h #include stdlib.h char* sortCharacters(char* s) { int n strlen(s); char* result (char*)malloc((n 1) * sizeof(char)); int idx 0; // 第一趟数字 for (int i 0; i n; i) { if (s[i] 0 s[i] 9) { result[idx] s[i]; } } // 第二趟字母 for (int i 0; i n; i) { if ((s[i] a s[i] z) || (s[i] A s[i] Z)) { result[idx] s[i]; } } // 第三趟其他符号 for (int i 0; i n; i) { if (!(s[i] 0 s[i] 9) !(s[i] a s[i] z) !(s[i] A s[i] Z)) { result[idx] s[i]; } } result[idx] \0; return result; } int main() { char* r1 sortCharacters(a1b2c3); char* r2 sortCharacters(Hi! How are you? 123?); char* r3 sortCharacters(Test123!!); printf(%s\n, r1); // 123abc printf(%s\n, r2); // 123HiHowareyou! ? ? printf(%s\n, r3); // 123Test!! free(r1); free(r2); free(r3); return 0; }运行结果 C语言/数据结构字符串题解：按字符类型重排（数字→字母→符号）——三趟扫描稳定分区
问题描述小明在整理班级的图书角时发现每本书的封面上都印有一个字符可能是字母、数字或符号。为了便于分类老师希望将这些字符按照类型重新排序先排列所有数字字符0-9然后是所有字母字符a-z, A-Z最后是其他符号字符。同时要求在同类型字符中保持它们在原始字符串中的相对顺序不变。请帮助小明设计一个算法实现字符串的字符类型排序。要求算法的时间复杂度应为 O(n)其中 n 是字符串的长度。尽量减少额外空间的使用以体现算法优化能力。测试样例样例1输入s a1b2c3输出123abc解释原始字符串中的数字字符 1,2,3 排在前面接着是字母字符 a,b,c它们都保持了原始顺序。样例2输入s Hi! How are you? 123?输出123HiHowareyou! ? ?解释数字字符 1,2,3 先输出然后是大写字母 H,H小写字母 i,o,w,a,r,e,y,o,u最后是符号字符 !, 空格、?, 空格、?。所有字符保持原始相对顺序。样例3输入s Test123!!输出123Test!!解释数字字符 1,2,3 排在最前然后是字母字符 T,e,s,t最后是符号字符 !,!。约束条件1 ≤ s.length ≤ 1000字符串 s 可能包含任意可打印 ASCII 字符ASCII 值从 32 到 126输出字符串应包含输入字符串中的所有字符包括空格等符号且同类型字符的相对顺序与输入一致程序代码#include stdio.h#include string.h#include stdlib.hchar* sortCharacters(char* s) {int n strlen(s);char* result (char*)malloc((n 1) * sizeof(char));int idx 0;// 第一趟数字for (int i 0; i n; i) {if (s[i] 0 s[i] 9) {result[idx] s[i];}}// 第二趟字母for (int i 0; i n; i) {if ((s[i] a s[i] z) || (s[i] A s[i] Z)) {result[idx] s[i];}}// 第三趟其他符号for (int i 0; i n; i) {if (!(s[i] 0 s[i] 9) !(s[i] a s[i] z) !(s[i] A s[i] Z)) {result[idx] s[i];}}result[idx] \0;return result;}int main() {char* r1 sortCharacters(a1b2c3);char* r2 sortCharacters(Hi! How are you? 123?);char* r3 sortCharacters(Test123!!);printf(%s\n, r1); // 123abcprintf(%s\n, r2); // 123HiHowareyou! ? ?printf(%s\n, r3); // 123Test!!free(r1);free(r2);free(r3);return 0;}#include stdio.h #include string.h #include stdlib.h char* sortCharacters(char* s) { int n strlen(s); char* result (char*)malloc((n 1) * sizeof(char)); int idx 0; // 第一趟数字 for (int i 0; i n; i) { if (s[i] 0 s[i] 9) { result[idx] s[i]; } } // 第二趟字母 for (int i 0; i n; i) { if ((s[i] a s[i] z) || (s[i] A s[i] Z)) { result[idx] s[i]; } } // 第三趟其他符号 for (int i 0; i n; i) { if (!(s[i] 0 s[i] 9) !(s[i] a s[i] z) !(s[i] A s[i] Z)) { result[idx] s[i]; } } result[idx] \0; return result; } int main() { char* r1 sortCharacters(a1b2c3); char* r2 sortCharacters(Hi! How are you? 123?); char* r3 sortCharacters(Test123!!); printf(%s\n, r1); // 123abc printf(%s\n, r2); // 123HiHowareyou! ? ? printf(%s\n, r3); // 123Test!! free(r1); free(r2); free(r3); return 0; }运行结果