字符串排序

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

规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。 如，输入： Type 输出： epTy

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

规则 3 ：非英文字母的其它字符保持原来的位置。 如，输入： By?e 输出： Be?y

样例输入：

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

输出：

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

本题要使用到稳定排序，这里顺便复习下归并排序：

#include <iostream> #include <string> #include <vector> using namespace std; void showVec(vector<char>& v){ for (auto ch : v){ cout << ch ; } cout << endl; } void __merge(vector<char>& v, char aux[], int l, int mid, int r){ // 拷贝一份 for (int i = l; i <= r; i++){ aux[i] = v[i]; } int i = l; int j = mid + 1; for (int k = l; k <= r; k++){ if (i > mid){ v[k] = aux[j]; // 左边没得啦 j++; } else if (j > r){ v[k] = aux[i]; // 右边没得啦 i++; } else if (toupper(aux[i]) <= toupper(aux[j])){ v[k] = aux[i]; i++; } else{ v[k] = aux[j]; j++; } } } // 对v，从[l..r]排序 void __merge_sort(vector<char>& v, char aux[], int l, int r){ if (l >= r)return; int mid = l + (r - l) / 2; __merge_sort(v, aux, l, mid); __merge_sort(v, aux, mid + 1, r); // 因为大小写无关，统一在大写字母是比较 if (toupper(v[mid]) > toupper(v[mid + 1])) __merge(v, aux, l, mid, r); } void mergeSort(vector<char>& v){ char *aux = new char[v.size()]; __merge_sort(v, aux, 0, v.size() - 1); delete[] aux; } int test(){ string s; while (getline(cin, s)){ vector<char> s_copy; for (int i = 0; i < s.size(); i++) if (isalpha(s[i]))s_copy.push_back(s[i]); // 稳定排序 mergeSort(s_copy); // 字符还原，只替换字母，其他字符不做处理 int j = 0; for (int i = 0; i < s.size(); i++) if (isalpha(s[i])){ s[i] = s_copy[j++]; } cout << s << endl; } return EXIT_SUCCESS; }

结果

A Famous Saying: Much Ado About Nothing(2012/8). A aaAAbc dFgghh: iimM nNn oooos Sttuuuy(2012/8).

使用系统提供的稳定排序

需要自己定义比较函数。

#include <iostream> #include <string> #include <algorithm> using namespace std; bool compare(const char &a1, const char &a2) { return tolower(a1) < tolower(a2); } int test(){ string s; while (getline(cin, s)){ vector<char> s_copy; for (int i = 0; i < s.size(); i++) if (isalpha(s[i]))s_copy.push_back(s[i]); // 稳定排序 stable_sort(s_copy.begin(), s_copy.end(), compare); //mergeSort(s_copy); // 字符还原，只替换字母，其他字符不做处理 int j = 0; for (int i = 0; i < s.size(); i++) if (isalpha(s[i])){ s[i] = s_copy[j++]; } cout << s << endl; } return EXIT_SUCCESS; }

结果与上面也是也一样