美團2020算法工程師程式設計題--字元串排序

題目描述：

生活中經常有需要将多個字元串進行排序的需要，比如将美團點評的部分業務名稱（外賣、打車、旅遊、麗人、美食、結婚、旅遊景點、教培、門票、酒店），用拼音表示之後按字母逆序排序。字母逆序指從z到a排序，比如對兩個字元串排序時，先比較第一個字母按字母逆序排z在a的前面，當第一個字母一樣時再比較第二個字母按字母逆序排，以此類推。特殊情況1)空字元串需排在最前面；2)若一個短字元串是另一個長字元串的字首則短字元串排在前面。請自行實作代碼進行排序，直接調用sort等排序方法将不得分且視為作弊。

輸入輸出描述：

輸入描述：

輸入為一行，由多個字元串以英文逗号拼接而成，最多不超過128個字元串且可能有重複。每個字元串由小寫字母a-z組成，可以為空，最長不超過128個字元。

輸出描述：

輸出一行，為排序之後的字元串，用逗号隔開

輸出輸出示例：

輸入示例：

waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei,menpiao,jiudian

輸出示例：

waimai,menpiao,meishi,lvyou,lvyoujingdian,liren,jiudian,jiehun,jiaopei,dache

題目分析：

題目還是有一定難度的，排序問題，關鍵點有兩個：

1.用什麼政策進行排序，冒泡、中值排序、快速排序、堆排序等

2.排序過程中要實作對連個元素的比較，這個比較的功能如何實作，對于簡單的數字排序，直接用>,<,=即可，但是對于字元串，這些邏輯功能可能并不好用，是以需要自己實作比較函數

關鍵：python中可以直接使用<,>,=對字元串進行排序，是以，可以使用簡單的冒泡排序算法實作

python實作代碼：

import sys
import re

line = sys.stdin.readline().strip()   # 注意要用strip()跳過輸入中開頭和結尾的空格或者換行符，否則輸出會受到影響
line = line.split(',')
for i in range(len(line)):
    for j in range(i+1, len(line)):
        if line[i] < line[j]:
            line[i], line[j] = line[j], line[i]
        if re.match(line[j], line[i]):
            line[i], line[j] = line[j], line[i]
for i in range(len(line)-1):
    if line[i] == '':
        for j in range(i, 0, -1):
            line[j] = line[j-1]
        line[0] = ''
        # line.remove(line[i])   #可替換上一個for循環
        # line.insert('')
res = ','.join(line)
print(res)