首页 > 试题广场 >

字符串排序

[编程题]字符串排序

热度指数：3360 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

生活中经常有需要将多个字符串进行排序的需要，比如将美团点评的部分业务名称（外卖、打车、旅游、丽人、美食、结婚、旅游景点、教培、门票、酒店），用拼音表示之后按字母逆序排序。字母逆序指从z到a排序，比如对两个字符串排序时，先比较第一个字母按字母逆序排z在a的前面，当第一个字母一样时再比较第二个字母按字母逆序排，以此类推。特殊情况1)空字符串需排在最前面；2)若一个短字符串是另一个长字符串的前缀则短字符串排在前面。请自行实现代码进行排序，直接调用sort等排序方法将不得分且视为作弊。

输入描述:

输入为一行，由多个字符串以英文逗号拼接而成，最多不超过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

备注:

算法知识视频讲解

Python

大傻蛋

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)

Python

ShadowAnt_TC

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)

Python

Spco

x = input().split(',')
# for i in x:
(3167)#     print(i)
for i in range(1, len(x)):
    for j in range(len(x) - i):
        if x[j] < x[j + 1]:
            x[j + 1], x[j] = x[j], x[j + 1]
            
for i in range(len(x) - 1):
    if len(x[i]) > len(x[i + 1]):
        if x[i][0:len(x[i + 1])] == x[i + 1]:
            x[i + 1], x[i] = x[i], x[i + 1]

for i in x:
    if i == '':
        print(',', end = "")

for i in range(len(x)):
    if x[i] == '':
        continue
    if i != len(x) - 1:
        print(x[i],end=',')
    else:
        print(x[i],end="")

80%的正确率。。。。

发表于 2020-03-20 23:36:51 回复(1)