生活中经常有需要将多个字符串进行排序的需要，比如将美团点评的部分业务名称（外卖、打车、旅游、丽人、美食、结婚、旅游景点、教培、门票、酒店），用拼音表示之后按字母逆序排序。字母逆序指从z到a排序，比如对两个字符串排序时，先比较第一个字母按字母逆序排z在a的前面，当第一个字母一样时再比较第二个字母按字母逆序排，以此类推。特殊情况1)空字符串需排在最前面；2)若一个短字符串是另一个长字符串的前缀则短字符串排在前面。请自行实现代码进行排序，直接调用sort等排序方法将不得分且视为作弊。
[编程题]字符串排序
- 热度指数：3343 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
输入为一行，由多个字符串以英文逗号拼接而成，最多不超过128个字符串且可能有重复。每个字符串由小写字母a-z组成，可以为空，最长不超过128个字符。
输出描述:
输出一行，为排序之后的字符串，用逗号隔开
示例1
输入
waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei,menpiao,jiudian
输出
waimai,menpiao,meishi,lvyou,lvyoujingdian,liren,jiudian,jiehun,jiaopei,dache
备注:
def isChange(str1, str2):
min_len = min(len(str1), len(str2))
for i in range(min_len):
if str1[i]>str2[i]:
return 0
elif str1[i]<str2[i]:
return 1
if len(str1) <= len(str2):
return 0
else:
return 1
strings = input().split(',')
str_len = len(strings)
for i in range(0, str_len-1):
for j in range(i+1, str_len):
change_flag = isChange(strings[i], strings[j])
if change_flag:
tmp = strings[i]
strings[i] = strings[j]
strings[j] = tmp
ans = ",".join(strings)
print(ans)
编辑于 2020-08-16 11:29:43
回复(0)
def isbig(s1, s2):
for c1, c2 in zip(s1, s2):
if c1 == c2:
continue
elif c1 > c2:
return True
else:
return False
def partition(index, slistcopy, start, end):
i = start - 1
for j in range(start, end):
if isbig(slistcopy[j], slistcopy[end]):
i += 1
slistcopy[i], slistcopy[j] = slistcopy[j], slistcopy[i]
index[i], index[j] = index[j], index[i]
i += 1
slistcopy[i], slistcopy[end] = slistcopy[end], slistcopy[i]
index[i], index[end] = index[end], index[i]
return i
def quicksort(index, slistcopy, start, end):
if start < end:
m = partition(index, slistcopy, start, end)
quicksort(index, slistcopy, start, m - 1)
quicksort(index, slistcopy, m + 1, end)
def sorts(slist):
length = len(slist)
slistcopy = slist.copy()
maxlength = 0
index = [i for i in range(length)]
for s in slistcopy:
maxlength = max(maxlength, len(s))
for i in range(length):
slistcopy[i] = slistcopy[i].ljust(maxlength, chr(ord('z')+1))
quicksort(index, slistcopy, 0, length - 1)
return index
while True:
try:
slist = list(input().split(','))
index = sorts(slist)
ans = []
for i in range(len(slist)):
ans.append(slist[index[i]])
print(','.join(ans))
except:
break quicksort 和 partition 是快排，比较是一次比较字符。
预处理比较重要，把所有字符串左对齐，在右侧补z后面那个字符。
发表于 2020-08-14 21:48:38
回复(0)
#include<iostream>
#include<algorithm>
#include <vector>
#include <string>
#include<sstream>
using namespace std;
//void swap(string& a, string& b) {
// string tmp;
// tmp = a;
// a = b;
// b = tmp;
//}
bool operator>=(const string& left, const string& right) {
if (left == "" && right != "") {
return true;
}
else if (left != "" && right == "") {
return false;
}
else if (left.size() <= right.size() && left == right.substr(0, left.size())) {
return true;
}
else if (left.size() > right.size() && right == left.substr(0, right.size())) {
return false;
}
else {
return left > right;
}
}
void sortstr(vector<string>& strs,int l,int r) {
int left = l, right = r;
if (l > r) {
return;
}
string sign = strs[left];
while (left < right) {
/*while (strs[right].compare(sign) && left<right) {
right--;
}
while (sign.compare(strs[left]) && left < right) {
left++;
}*/
while (strs[right]>=sign && left < right) {
right--;
}
while (sign>=strs[left] && left < right) {
left++;
}
if (left < right) {
swap(strs[left], strs[right]);
}
}
swap(strs[l], strs[left]);
sortstr(strs, l, left - 1);
sortstr(strs, left + 1, r);
}
int main() {
vector<string> strs;
string word,line;
while (getline(cin,line)) {
if (line.size() == 0) break;
istringstream record(line);
for (int i = 0;i<line.size();i++) {
if (line[i] == ',') {
strs.push_back(word);
word = "";
}
else if(i == line.size()-1){
word += line[i];
strs.push_back(word);
word = "";
break;
}
else {
word += line[i];
}
}
sortstr(strs, 0, strs.size()-1);
for (int j = strs.size()-1; j >=0; j--) {
if(j>0)
cout << strs[j] << ',';
else
cout << strs[j] << endl;
}
}
}
编辑于 2020-03-19 17:38:06
回复(0)
python解法
import re
temp = input()
emp = temp.split(',')
emp_2 = emp
for i in range(len(emp)):
for j in range(i, len(emp)):
if emp[i] in emp[j]:
continue
if emp[i] < emp[j]:
emp[i],emp[j] = emp[j],emp[i]
if re.match(emp[j], emp[i]):
emp[i], emp[j] = emp[j],emp[i]
for i in range(len(emp)-1):
if emp[i] == '':
for k in range(i,0,-1):
emp[k] = emp[k-1]
emp[0] = ''
rst = ','.join(emp)
print(rst)
发表于 2020-03-12 22:49:10
回复(8)
python（冒泡）：
s = input()
s_list = s.split(',')
n = len(s_list)
for i in range(n, 0, -1):
for j in range(1, i):
if s_list[j] == "":
s_list[j], s_list[j-1] = s_list[j-1], s_list[j]
continue
if s_list[j-1] == "":
continue
if s_list[j] > s_list[j-1]:
s_list[j], s_list[j-1] = s_list[j-1], s_list[j]
if s_list[j] in s_list[j-1] and s_list[j][0]==s_list[j-1][0]:
s_list[j], s_list[j-1] = s_list[j-1], s_list[j]
print(','.join(s_list))
发表于 2021-03-13 12:59:53
回复(0)
python简洁代码
import sys
def sort(s1, s2):
n = min(len(s1), len(s2))
for i in range(n):
if s1[i] > s2[i]:
return False
elif s1[i] < s2[i]:
return True
if len(s1) > len(s2):
return True
else:
return False
words = [x for x in input().split(',')]
n = len(words)
for i in range(n):
for j in range(i + 1, n):
if sort(words[i], words[j]):
words[i], words[j] = words[j], words[i]
print(','.join(words))
发表于 2023-06-21 18:53:23
回复(0)
#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool BLargeWord(string str1, string str2) {
if (str1 == "")return true;
int strlength = min(str1.length(), str2.length());
for (int i = 0; i < strlength; i++) {
if (str1[i] > str2[i]) return true;
else if (str1[i] < str2[i])return false;
}
if (str1.length() < str2.length()) return true;
return false;//完全相等的字符返回false;
}
void TM25() {
string instr;
vector<string> worlds;
getline(cin, instr);
string tempworld = "";
//分割字符
for (int i = 0; i < instr.length(); i++) {
if (instr[i] == ',') {
worlds.push_back(tempworld);
tempworld = "";
}
else tempworld.push_back(instr[i]);
if (i == instr.length() - 1) worlds.push_back(tempworld);
}
//排序
vector<string> sortedWords;
sortedWords.push_back(worlds[0]);
for (int i = 1; i < worlds.size(); i++) {
for (int j = 0; j < sortedWords.size(); j++) {
if (BLargeWord(worlds[i], sortedWords[j])) {
sortedWords.insert(sortedWords.begin() + j, worlds[i]);
break;
}
if (j == sortedWords.size() - 1) {
sortedWords.push_back(worlds[i]);
break;
}
}
}
//输出
for (int i = 0; i < sortedWords.size(); i++) {
if (i == sortedWords.size() - 1)cout << sortedWords[i] << endl;
else cout << sortedWords[i] << ",";
}
}
int main(){
TM25();
return 0;
}
发表于 2023-03-09 18:24:45
回复(0)
import java.util.Scanner;
/**
* 字符串从大到小排序
*
* @author XML_Jeff
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
String[] strs = str.split(",");
quickSort(strs, 0, strs.length - 1);
for (int i = 0; i < strs.length; i++) {
if (i < strs.length - 1) {
System.out.print(strs[i] + ",");
} else {
System.out.println(strs[i]);
}
}
}
public static void quickSort(String[] arr, int low, int high) {
if (low < high) {
int index = getIndex(arr, low, high);
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
// 得到基准数的位置
public static int getIndex(String[] arr, int low, int high) {
String temp = arr[low];
while (low < high) {
while (low < high && compareString(temp, arr[high])) {
high--;
}
arr[low] = arr[high];
while (low < high && compareString(arr[low], temp)) {
low++;
}
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
/**
* 比较str1是否大于等于str2
*
* @param str1
* @param str2
* @return
*/
public static boolean compareString(String str1, String str2) {
if (str1.equals("")) {
return true;
}
int min = Math.min(str1.length(), str2.length());
for (int i = 0; i < min; i++) {
if (str1.charAt(i) > str2.charAt(i)) {
return true;
} else if (str1.charAt(i) == str2.charAt(i)) {
continue;
} else {
return false;
}
}
if (str1.length() > str2.length()) {
return false;
}
return true;
}
}
/**
* 字符串从大到小排序
*
* @author XML_Jeff
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
String[] strs = str.split(",");
quickSort(strs, 0, strs.length - 1);
for (int i = 0; i < strs.length; i++) {
if (i < strs.length - 1) {
System.out.print(strs[i] + ",");
} else {
System.out.println(strs[i]);
}
}
}
public static void quickSort(String[] arr, int low, int high) {
if (low < high) {
int index = getIndex(arr, low, high);
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
// 得到基准数的位置
public static int getIndex(String[] arr, int low, int high) {
String temp = arr[low];
while (low < high) {
while (low < high && compareString(temp, arr[high])) {
high--;
}
arr[low] = arr[high];
while (low < high && compareString(arr[low], temp)) {
low++;
}
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
/**
* 比较str1是否大于等于str2
*
* @param str1
* @param str2
* @return
*/
public static boolean compareString(String str1, String str2) {
if (str1.equals("")) {
return true;
}
int min = Math.min(str1.length(), str2.length());
for (int i = 0; i < min; i++) {
if (str1.charAt(i) > str2.charAt(i)) {
return true;
} else if (str1.charAt(i) == str2.charAt(i)) {
continue;
} else {
return false;
}
}
if (str1.length() > str2.length()) {
return false;
}
return true;
}
}
发表于 2021-09-27 16:00:50
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
vector <string> vec;
string s;
cin>>s;
string a;
for (char ch:s){
if(ch==',') {
vec.push_back(a);
a="";
}
else {
a+=ch;
}
}
vec.push_back(a);
//冒泡法
for (int i=0;i<vec.size()-1;i++){
for (int j=0;j<vec.size()-1-i;j++){
int pos=vec[j+1].find(vec[j]);
int pos1=vec[j].find(vec[j+1]);
if(vec[j]<vec[j+1] && pos!=0) swap(vec[j],vec[j+1]);
else {
if (pos1==0) swap(vec[j],vec[j+1]);
}
}
}
for(int i=0;i<vec.size()-1;i++){
cout<<vec[i]<<',';
}
cout<<vec[vec.size()-1]<<endl;
return 0;
}
using namespace std;
int main(){
vector <string> vec;
string s;
cin>>s;
string a;
for (char ch:s){
if(ch==',') {
vec.push_back(a);
a="";
}
else {
a+=ch;
}
}
vec.push_back(a);
//冒泡法
for (int i=0;i<vec.size()-1;i++){
for (int j=0;j<vec.size()-1-i;j++){
int pos=vec[j+1].find(vec[j]);
int pos1=vec[j].find(vec[j+1]);
if(vec[j]<vec[j+1] && pos!=0) swap(vec[j],vec[j+1]);
else {
if (pos1==0) swap(vec[j],vec[j+1]);
}
}
}
for(int i=0;i<vec.size()-1;i++){
cout<<vec[i]<<',';
}
cout<<vec[vec.size()-1]<<endl;
return 0;
}
发表于 2021-07-28 21:08:25
回复(0)
使用冒泡排序
import sys
import re
line = sys.stdin.readline().strip() # 注意要用strip()跳过输入中开头和结尾的空格或者换行符，否则输出会受到影响
keywords = line.split(',')
for i in range(len(keywords)):
for j in range(i + 1, len(keywords)):
if keywords[i] < keywords[j]:
keywords[i], keywords[j] = keywords[j], keywords[i]
if re.match(keywords[j], keywords[i]):
keywords[i], keywords[j] = keywords[j], keywords[i]
for i in range(len(keywords) - 1):
if keywords[i] == '':
for j in range(i, 0, -1):
keywords[j] = keywords[j - 1]
keywords[0] = ''
res = ','.join(keywords)
print(res)
发表于 2020-10-15 17:06:31
回复(0)
s=list(input().split(','))
def axiao(a,b):
l1=len(a)
l2=len(b)
for i in range(min(l1,l2)):
if a[i]<b[i]:
return True
elif a[i]>b[i]:
return False
else:
continue
if l1>=l2:
return True
else:
return False
def quicksort(s):
if not s:
return []
p=s[0]
s.remove(p)
left=[i for i in s if axiao(i,p)]
right=[i for i in s if not axiao(i,p)]
return quicksort(left)+[p]+quicksort(right)
print(','.join(quicksort(s)[::-1]))
基于递归快排，针对各种排序题都适用，只要把大小定义函数更改
发表于 2020-08-13 01:28:08
回复(0)
import sys
s = sys.stdin.readline().strip("\n").split(",")
# 自行实现排序，快排
def quickSort(s):
if len(s) <= 1:
return s
else:
left, right = [], []
for i in range(1, len(s)):
if s[i] == "" or (s[i] >= s[0] and not s[i].startswith(s[0])) or s[0].startswith(s[i]):
left.append(s[i])
else:
right.append(s[i])
return quickSort(left) + s[0:1] + quickSort(right)
s = quickSort(s)
for i in range(len(s)):
if i < len(s) - 1:
print(s[i], end=",")
else:
print(s[i])
编辑于 2020-07-24 00:08:20
回复(0)
n = input() str_list = n.split() print(str_list) for i in range(0,len(str_list)): for j in range(i+1,len(str_list)): if str_list[j]>str_list[i]: str_list[j],str_list[i] = str_list[i],str_list[j] print(str_list)
发表于 2020-07-21 14:25:04
回复(0)
import java.util.Scanner;
public class ZiFuChuanPaiXu {
public static boolean bijiao(String str1,String str2){
// lvyoujingdian<lvyou
int length1 = str1.length();//
int length2 = str2.length();//5
int min = Math.min(length1, length2);//4
int i = 0;
while(i<min){
if(str1.charAt(i)<str2.charAt(i)){
return true;
}else if(str1.charAt(i)==str2.charAt(i)){
i++;
}else{
return false;
}
}
if(i==length1){
return false;
}
return true;
}
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
String str = scan.next();
String []str3 = str.split(",");
int length = str3.length;
for(int i = 0;i<length;i++){
for(int j = 0;j<length-1-i;j++){
if(bijiao(str3[j+1],str3[j])){
System.out.println(str3[j]+"和"+str3[j+1]+"交换");
String temp = str3[j+1];
str3[j+1] = str3[j];
str3[j] = temp;
}
}
}
for(int i =str3.length-1;i>=0;i--){
if(i==0){
System.out.print(str3[i]);
}else{
System.out.print(str3[i]+",");
}
}
}
}
public class ZiFuChuanPaiXu {
public static boolean bijiao(String str1,String str2){
// lvyoujingdian<lvyou
int length1 = str1.length();//
int length2 = str2.length();//5
int min = Math.min(length1, length2);//4
int i = 0;
while(i<min){
if(str1.charAt(i)<str2.charAt(i)){
return true;
}else if(str1.charAt(i)==str2.charAt(i)){
i++;
}else{
return false;
}
}
if(i==length1){
return false;
}
return true;
}
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
String str = scan.next();
String []str3 = str.split(",");
int length = str3.length;
for(int i = 0;i<length;i++){
for(int j = 0;j<length-1-i;j++){
if(bijiao(str3[j+1],str3[j])){
System.out.println(str3[j]+"和"+str3[j+1]+"交换");
String temp = str3[j+1];
str3[j+1] = str3[j];
str3[j] = temp;
}
}
}
for(int i =str3.length-1;i>=0;i--){
if(i==0){
System.out.print(str3[i]);
}else{
System.out.print(str3[i]+",");
}
}
}
}
发表于 2020-07-14 19:00:38
回复(0)
#include <bits/stdc++.h>
using namespace std;
bool smaller(string str1, string str2){
if(str1.length() == 0) return false;
if(str2.length() == 0) return true;
//if(str1[0] == '\0') return true;
//if(str2[0] == '\0') return false;
if(str1[0] < str2[0]) return true;
if(str1[0] > str2[0]) return false;
else return smaller(str1.substr(1,str1.length()-1), str2.substr(1,str2.length()-1));
}
void change(vector<string> &vec, int i, int j){
string temp(vec[i]);
vec[i].assign(vec[j]);
vec[j].assign(temp);
return;
}
int main(){
vector<string> vec;
int j = 0, i = 0;
string s;
cin >> s;
for(; j < s.length(); ++j) {
if(s[j] == ',') {
vec.push_back(s.substr(i, j - i));
i = j + 1;
}
}
vec.push_back(s.substr(i, j - i));
int l = (int)vec.size();
for(int i = 0; i<l; i++){
for(int j = 0; j<l-1; j++){
if(smaller(vec[j],vec[j+1])) change(vec, j, j+1);
}
}
for(int i = 0; i<l-1; i++){
cout << vec[i] << ',';
}
cout << vec[l-1];
return 0;
}
发表于 2020-05-12 00:47:29
回复(0)
import re
string=input().split(',')
for i in range(len(string)):
for j in range(i+1,len(string)):
if string[i]<string[j]:
string[i],string[j]=string[j],string[i]
if re.match(string[j],string[i]):
string[i],string[j]=string[j],string[i]
print(','.join(string))
string=input().split(',')
for i in range(len(string)):
for j in range(i+1,len(string)):
if string[i]<string[j]:
string[i],string[j]=string[j],string[i]
if re.match(string[j],string[i]):
string[i],string[j]=string[j],string[i]
print(','.join(string))
发表于 2020-05-06 11:57:14
回复(0)
基数排序
def solution(data):
lc = list('abcdefghijklmnopqrstuvwxyz ')
lc = lc[::-1]
dic = {}
for i in range(len(lc)):
dic[i] = []
maxL = 0
for i in range(len(data)):
if len(data[i]) > maxL:
maxL = len(data[i])
for i in range(len(data)):
data[i] = data[i].ljust(maxL, ' ')
for i in range(maxL-1, -1, -1):
for j in range(len(data)):
idx = lc.index(data[j][i])
dic[idx].append(data[j])
new_data = []
for k in dic:
new_data += dic[k]
dic[k] = []
data = new_data
print(','.join(x.strip() for x in data))
if __name__ == '__main__':
data = input().strip().split(',')
solution(data)
发表于 2020-04-28 17:55:58
回复(0)
#include<stdio.h>
#include<string.h>
#define ITEMS 128
#define LENGTH 129
char cmp(char* a, char* b){
int i = 0; /*自定义的比较函数，类似strcmp*/
do {
if (a[i] != b[i])
if (a[i] == '\0')
return 1;
else if (b[i] == '\0')
return -1;
else
return a[i] - b[i];
} while (a[i] != '\0' && b[i++] != '\0');
return 0;
}
int main(){
char ch=0;
int i=0;
struct list {char a[LENGTH];};
struct list a[ITEMS];
struct list mid; /*用结构类型可以方便地换序*/
for (i=0;i < ITEMS&&ch!='\n';i++) /*输入*/
{
a[i].a[0] = '\0';
for (int j = 0;j < LENGTH - 1 &&
(strchr(",\n", ch = getchar()) == NULL);j++)
a[i].a[j] = ch, a[i].a[j + 1] = '\0';
}
for (int e = 0;e < i;e++)
for (int m = e + 1;m < i;m++)
if (cmp(a[e].a, a[m].a) < 0)
mid = a[e], a[e] = a[m], a[m] = mid; /*排序*/
for (int n = 0;n < i;n++)
if (n < i - 1)
printf("%s,", a[n].a); /*输出*/
else
printf("%s", a[n].a);
return 0;
} 平安通过所有用例
编辑于 2020-04-27 14:26:29
回复(0)
问题信息
通过挑战的用户
-
2023-03-09 21:55:23 -
2023-03-09 18:22:44
-
2023-03-09 14:10:22
-
2023-02-23 12:36:23
-
2023-01-09 12:59:51
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
