题解 | #字符串排序#
字符串排序
https://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584
获取字符串后,将英文字母提取到vector中,然后进行排序,排序使用的是归并排序(忽略大小写),然后将字符串输出,非字母位置输出原字符。
#include <cctype> #include <iostream> #include <vector> using namespace std; void sort_l(vector<char> & letters, int start, int end); void merage(vector<char> & letters, int start, int end); int main() { string s; getline(cin, s); vector<char> letters; for (char letter : s) { if (isalpha(letter)) { letters.push_back(letter); } } sort_l(letters, 0, letters.size() - 1); int count = 0; for (int i = 0; i < s.length(); i++) { if (isalpha(s.at(i))) { cout << letters.at(count++); } else { cout << s.at(i); } } return 0; } void sort_l(vector<char> & letters, int start, int end) { if (start == end) { return; } sort_l(letters, start, (start + end) / 2); sort_l(letters, (start + end) / 2 + 1, end); merage(letters, start, end); } void merage(vector<char> & letters, int start, int end) { vector<char> temp; int start1 = start; int start2 = (start + end) / 2 + 1; int count = 0; int start_t; while (start1 < (start + end) / 2 + 1 && start2 <= end) { if (toupper(letters.at(start1)) <= toupper(letters.at(start2))) { temp.push_back(letters.at(start1)); start1++; } else { temp.push_back(letters.at(start2)); start2++; } count++; } if (start1 == (start + end) / 2 + 1) { start_t = start2; } else { start_t = start1; } while (count < end - start + 1) { temp.push_back(letters.at(start_t++)); count++; } count = 0; for (int i = start; i <= end; i++) { letters.at(i) = temp.at(count++); } } // 64 位输出请用 printf("%lld")
中等(算法题解) 文章被收录于专栏
中等难度题目