题解 | 字符串排序

1.这个方法最简单，直接调用sorted函数。
'''import sys

n=int(input())
words=[input().split()[0] for i in range(n)]
for word in sorted(words):
    print(word)'''
2.我自己写的，复杂度是O(n^2 * max_len) ，最后一个案例超时了。
'''import sys
n=int(input())
words=[input().split()[0] for i in range(n)]
max_len=0
for word in words:
    if max_len<len(word):
        max_len=len(word)
#print(min(3,5))
for i in range(max_len):
    for j in range(n):
        for k in range(j+1,n):
            if(i<len(words[k]) or  i<len(words[j])):
                if(i<len(words[k]) and  i<len(words[j])):
                    if words[j][i] >words[k][i]  :
                        if i==0:
                            temp=words[j]
                            words[j]=words[k]
                            words[k]=temp
                        else:
                            if(words[j][0:i]==words[k][0:i]):
                                temp=words[j]
                                words[j]=words[k]
                                words[k]=temp

                elif (i-min(len(words[k]),len(words[j])))==0:
                    if i==0:
                        if(len(words[k])>len(words[j])):
                            if(k<j):
                                temp=words[j]
                                words[j]=words[k]
                                words[k]=temp
                        else:
                            if(k>j):
                                temp=words[j]
                                words[j]=words[k]
                                words[k]=temp
                    else:
                        if(words[j][0:i]==words[k][0:i]):
                            #print(words[j],words[k],i,words[j][0:i],words[k][0:i])
                            if(len(words[k])>len(words[j])):
                                if(k<j):
                                    temp=words[j]
                                    words[j]=words[k]
                                    words[k]=temp
                            else:
                                if(k>j):
                                    temp=words[j]
                                    words[j]=words[k]
                                    words[k]=temp
               # print((words[j][0]))
for word in words:
    print(word)
    None'''


3.gpt给的，好像用了什么快速排序（quicksort）或归并排序（mergesort），没看懂。总复杂度是 O(n log n)。不过我借鉴cmp函数用for循环写了一个，就是4.
'''def cmp(a, b):
    min_len = min(len(a), len(b))
    for i in range(min_len):
        if a[i] != b[i]:
            return a[i] < b[i]
    return len(a) < len(b)

def quick_sort(arr, left, right):
    if left >= right:
        return
    pivot = arr[left]
    i, j = left, right
    while i < j:
        while i < j and cmp(pivot, arr[j]):
            j -= 1
        while i < j and not cmp(pivot, arr[i]):
            i += 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
    arr[left], arr[i] = arr[i], arr[left]
    quick_sort(arr, left, i - 1)
    quick_sort(arr, i + 1, right)

# 输入
n = int(input())
words = [input().split()[0] for _ in range(n)]

# 排序
quick_sort(words, 0, n - 1)

# 输出
for word in words:
    print(word)'''

4.我借鉴3的cmp函数用for循环写了一个，复杂度是O(n² × L)，L 是平均字符串长度。这个能通过
def cmp(a, b):
    min_len = min(len(a), len(b))
    for i in range(min_len):
        if a[i] != b[i]:
            return a[i] < b[i]
    return len(a) < len(b)


# 输入
n = int(input())
words = [input().split()[0] for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        if not cmp(words[i], words[j]):
            temp=words[j]
            words[j]=words[i]
            words[i]=temp
for word in words:
    print(word)