【华为OD机试】HJ26 字符串排序

描述

编写一个程序，将输入字符串中的字符按如下规则排序。

规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。

如，输入： Type 输出： epTy

规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。

如，输入： BabA 输出： aABb

规则 3 ：非英文字母的其它字符保持原来的位置。
 

如，输入： By?e 输出： Be?y

数据范围：输入的字符串长度满足 1≤n≤1000 

输入描述：

输入字符串

输出描述：

输出字符串

示例1

输入：

A Famous Saying: Much Ado About Nothing (2012/8).

输出：

A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

思路：

根据三个规则，规则1要对字母进行排序，不区分大小写，这个通过sort函数加重写cmp完成，规则2要按照输入时的顺序进行排序，那么就要记录这个字母的位置，可以用结构体完成，规则3就直接把非字母跳过就行。

代码：

#include
using namespace std;
 
char s[1005];
 
struct ac {
	int num;
	char c;
} a[1005];
 
bool cmp(ac a, ac b) {
	int x, y;
	if (a.c >= 'a' && a.c <= 'z')
		x = a.c - 'a';
	else
		x = a.c - 'A';
 
	if (b.c >= 'a' && b.c <= 'z')
		y = b.c - 'a';
	else
		y = b.c - 'A';
	if (x == y)
		return a.num < b.num;
	else
		return x < y;
}
 
int main() {
	int  i, j = 0, k = 0;
	string str;
 
	getline(cin, str);
	for (i = 0; i < str.length(); i++) {
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z' ) {
			a[j].c = str[i];
			a[j].num = i;
			j++;
		}
	}
	sort(a, a + j, cmp);
	for (i = 0; i < str.length(); i++) {
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z' ) {
			cout << a[k].c;
			k++;
		} else
			cout << str[i];
 
	}
	return 0;
}