list 和 dict
from IPython.display import Image
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Image(filename = 'Desktop/快乐研一/python/list_dict.jpg', width=300, height=300)
区别点
python最重要的两种数据类型，注意的点：
- dict内部没有顺序关系
list
- 按索引取值赋值：，随机访问，优
- 添加：append优于+
"+"事实上生成了一个新的列表再复制过去（类似x+=1优于x = x+1）
- 删除pop()优于pop(i)
dict
- 取值get赋值set。 dict.get('key值') 键值存在，则返回对应值
- 检索in， key in dict
简单小题熟悉python
### 题目一
# 输出一个数，即他们的商，保持小数点后4位（%.4f）
# 如果除数为0，则输出：NA（两个字母）
numerator = float(input("请输入分子"))
denominator = float(input("请输入分母"))
if denominator!=0:
num = numerator/denominator
print('%.4f' % num)
else:
print("NA")
请输入分子3
请输入分母5
0.6000
### 题目二
# 给出行数和列数，打印一个由*号构成的实心矩形
# 输入格式: 一行，用空格隔开的两个整数m、n
m,n = map(int,input("请输入两个整数，用空格隔开:").split())
for i in range(0,n): print( "*"*m)
### 题目三
# 输入格式:一行，由空格隔开的一系列整数，数量2个以上，找到最小的数
lst = [] #定义一个空列表
str = input("请输入一列整数，用空格隔开:")
lst1 = list(map(int, str.split())) # 用空格分割
lst1.sort()
print("最小值为:{}".format(lst1[0]))
变位词判断问题
## 我的思路
# 对于26个字母，分别计算每个字母出现次数——26维——对比两个词对应向量是否一致。
# 定义函数
def anagramSolution1(s_1,s_2):
s1 = list(s_1) ## 转化为list
s2 = list(s_2)
isanagram = False
if len(s1)==len(s2):
zimu = list(map(chr, range(ord('a'), ord('z')+1))) ## 获取26个字母的序列
count1 = [0]*len(zimu)
count2 = [0]*len(zimu)
## 统计26个字母在字符中出现次数
for j in range(0,len(zimu)):
for i in range(0,len(s1)):
if zimu[j] == s1[i]: count1[j] += 1
if zimu[j] == s2[i]: count2[j] += 1
if count1==count2: isanagram = True ## 对比出现次数是否一致
return isanagram
# 测试
anagramSolution1("aabb","abb")
anagramSolution1("aabbzz","abzabz")
anagramSolution1("python","typhon")
False
True
True
## 其他思路——code最短的方法
# 转化为list后排序，然后对比
def anagramSolution2(s_1,s_2):
s1 = list(s_1) ## 转化为list
s2 = list(s_2)
s1.sort()
s2.sort()
isanagram = False
if s1==s2: isanagram = True
return isanagram
# 测试
anagramSolution2("aabb","abb")
anagramSolution2("aabbzz","abzabz")
anagramSolution2("python","typhon")
False
True
True
一些基本结构
线性结构：数据项之间只存在先后次序关系，区别在于增减方式
- 栈 stack：加入和移除都在同一段，“后进先出”e.g.叠盘子
- 队列 queue
- 双端队列 deque
- 列表 list
栈
- 将ADT Stack实现为python 的一个class
Image(filename = 'Desktop/快乐研一/python/stack.jpg', width=300, height=300)
## py - STACK
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items ==[]
def push(self, item):
self.items.append(item) # append o(1)
def pop(self):
return self.items.pop() # pop o(1)
def peek(self):
return self.items[-1] # 小知识：-1也是取出list中最后一个
def size(self):
return len(self.items)
# 实例化
s = Stack()
s.push(4)
s.push('yyy')
print(s.items)
print(s.size())
[4, 'yyy']
2
括号匹配
## 简单应用——括号匹配
def parChecker(strings_):
strings = list(strings_)
s = Stack()
stillbalance = True
i=0
while i < len(strings) and stillbalance:
if strings[i]=="(":
s.push(strings[i])
else:
if strings[i]==")":
if s.isEmpty()==True: stillbalance = False # 没有匹配的左括号，就F
else: s.pop() # 如果匹配就pop掉
i =i+1
results = stillbalance and s.isEmpty() # 如果多余左括号，也要F
return(results,stillbalance,s.isEmpty())
# 测试
parChecker("2(2+x)x(x(sss))")
parChecker("2(2+x)x(x)(sss))")
(True, True, True)
(False, False, True)
## 复杂应用——括号匹配（[{
strings = list("2(s[x()x{er[]c}]s)0")
# 同上，如果多出一个左或者右括号，F
# (] pop时如果最近的两个括号不是一类，也F
# 了解字符串的in 和 index
left = "({["
right = ")}]"
a = ")"
a in right,a in left,left.index("{")==right.index("}"),left.index("[")==right.index("}")
#######################
## 修改上面的函数为 ##
def parChecker2(strings_):
strings = list(strings_)
s = Stack()
left = "({["
right = ")}]"
stillbalance = True
i=0
while i < len(strings) and stillbalance:
if strings[i] in left:
s.push(strings[i])
else:
if strings[i] in right:
if s.isEmpty()==True:
stillbalance = False
else:
tmp = s.pop()
if left.index(tmp)!=right.index(strings[i]): stillbalance = False # 如果括号类型不匹配，F
i =i+1
results = stillbalance and s.isEmpty()
return(results, stillbalance, s.isEmpty())
# 测试
parChecker2("2(s[x()x{er[]c}]s)0()")
parChecker2("22{()}2asda[]2(")
parChecker2("2(s[x()x{er[]c}]s)0{]")
(True, False, True, False)
(True, True, True)
(False, True, False)
(False, False, True)
二进制
- 回忆整数二进制的含义，十进制转化为二进制：不断除以2，得到余数和需要的输出时反转关系——栈
- 栈反转次序：每次push进去一个，先输入的压在后面了
# 函数十进制转二进制
def mybinary(num):
s=Stack()
while num>0:
t = num % 2 # 取余数
s.push(t)
num = num//2 # 整数除
return(s.items[::-1])
# 测试
mybinary(2)
mybinary(233)
[1, 0]
[1, 1, 1, 0, 1, 0, 0, 1]
一维消消乐
逐个消去相邻的相同字符对
- 输入一个字符串，可能带有相邻的相同字符，如“aabbbc”
- 输出一个字符串，消去了相邻的成对字符，如“bc”
- abbacddccc00，这里bb被消了以后，第二个a挨上来了，所以两个a也相邻，同样消去
## 定义函数
def xiaoxiaole(string):
strings = list(string)
s =Stack()
s.push(strings[0])
# 消消乐
for i in range(1, len(strings)):
if s.isEmpty()==True:
s.push(strings[i])
else:
if strings[i]!=s.peek():
s.push(strings[i])
else: s.pop()
# 输出
if s.isEmpty()==True:
results = "None"
else:
results=""
for j in range(0,s.size()):
results = results + s.items[j]
return(results)
## 测试
xiaoxiaole("abbacddccc00")
xiaoxiaole("beepooxxxyz")
'None'
'bpxyz'
棒球比赛记录
给定一个字符串列表，每个字符串可以是以下四种类型之一：
- 整数（一轮的得分）：直接表示您在本轮中获得的积分数。
- "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
- "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
- "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效回合的分数是无效的，应该被移除。
需要返回你在所有回合中得分的总和
def baseballscore(string):
score = Stack()
for i in range(0,len(string)):
if string[i].isdigit() or string[i].lstrip('-').isdigit():
score.push(int(string[i]))
else:
if string[i]=="C":
score.pop()
if string[i]=="+":
score.push(score.items[-1]+score.items[-2])
if string[i]=="D":
score.push(score.peek()*2)
return(sum(score.items))
baseballscore(["5","2","C","D","+"])
baseballscore(["5","-2","4","C","D","9","+","+"])
30
27
队列
添加发生在尾端，移除发生在首端“先进先出”
Image(filename = 'Desktop/快乐研一/python/queue1.jpg', width=300, height=300)
# 用list[0]作为队尾
class Queue:
def __init__(self):
self.items =[]
def isEmpty(self):
return self.items == []
def enqueue(self, item): # 复杂度o(n)
return self.items.insert(0,item)
def dequeue(self): # 复杂度o1
return self.items.pop()
def size(self):
return len(self.items)
击鼓传花/热土豆/约瑟夫问题
- 输入：参加游戏人列表、每轮传递次数num
- 输出：最后剩下的人名
- 思路：传递时队首的人移除再从队尾加入，当传递num次时从队首移除但是不加入队尾，如此反复。
## 定义函数
def hotpotato(namelist, num):
thequeue = Queue()
for name in namelist:
thequeue.enqueue(name) # 初始化队列
while thequeue.size() >1:
for i in range(0,num): # 开始一轮
thequeue.enqueue(thequeue.dequeue())
thequeue.dequeue() # 每轮结束踢出队首
return(thequeue.dequeue()) # 最后剩下的
## 测试
hotpotato(['a','b','c','d','e','f','g','h'], 7)
'd'
打印模拟
- 按照概率生成打印作业，加入队列
- 如果打印机空闲，则取队首打印，打印机忙碌，记录等待时间
- 如果打印机忙碌，则按照打印速度进行
- 如果完成，打印机进入空闲
需要计算平均等待&打印时间：
- 生成作业+开始打印都要记录
- 记录页数，除以打印时间
# 1.生成作业（ 180秒内会有一次作业）
import random
def newTask():
num = random.randrange(1,61)
if num==6:
return True # 以1/60的概率生成作业
else: # 59/60的概率不生成作业
return False
# 2.记录打印时间、页数、等待时间
class Task:
def __init__(self, time):
self.timestamp = time # 记录时间
self.pages = random.randrange(1,21)
def getStamp(self):
return self.timestamp
s
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime - self.timestamp
# 3.生成打印机，记录打印进行、是否忙、开始打印新作业
class Printer():
def __init__(self,ppm): # ppm——打印速度
self.pagerate = ppm # 打印速度
self.currentTask = None # 当前的打印任务
self.timeRemaining = 0 # 正在进行的任务还需要多久
def tick(self): # 打印进行
if self.currentTask!=None: # 对于当前的打印任务
self.timeRemaining = self.timeRemaining - 1 # 当前任务进行中
if self.timeRemaining <=0: # 打印完毕
self.currentTask = None
def busy(self): # 判断打印机是不是空闲
if self.currentTask !=None:
return True
else:
return False
def startNext(self,newtask): # 打印新的作业
self.currentTask = newtask
self.timeRemaining = newtask.getPages()*60/self.pagerate
#### 正式模拟
def simulation(numSeconds, pagesPerMinute): # 总时长，打印机每分钟打印页数
labprinter = Printer(pagesPerMinute) # 初始化打印机
printQueue = Queue() # 初始化一个空队列，准备存储打印队列
waitingtime = [] # 初始化一个列表，准备存储每个task的等待时间
# 开始模拟
for currentSecond in range(numSeconds) : # 在整个时间内
# 1.生成任务
if newTask(): # 每秒随机生成任务，如果成功生成了新任务
task = Task(currentSecond) # 记录任务的生成时间
printQueue.enqueue(task) # 任务队列增加一个
# 2.打印机制
if(not labprinter.busy()) and(not printQueue.isEmpty()):
# 如果打印机处于空闲，并且任务队列不为空，就开始打印
nexttask = printQueue.dequeue() # 从队首拿出这个新任务
waitingtime.append(nexttask.waitTime(currentSecond))# 更新等待时间
labprinter.startNext(nexttask)
labprinter.tick() # 有正在进行的任务，就进行，没有就标记完成
if not printQueue.isEmpty():print("%6d s，还有%d个任务"%(currentSecond, printQueue.size()))
# 计算平均等待时间
averageWait = sum(waitingtime)/len(waitingtime)
print("平均等待时间 %6.2f s，还剩 %d 个任务"%(averageWait, printQueue.size()))
simulation(500,15)
116 s，还有1个任务
117 s，还有1个任务
118 s，还有1个任务
119 s，还有1个任务
120 s，还有1个任务
121 s，还有1个任务
122 s，还有1个任务
123 s，还有1个任务
124 s，还有1个任务
125 s，还有1个任务
126 s，还有1个任务
127 s，还有1个任务
128 s，还有1个任务
129 s，还有1个任务
130 s，还有1个任务
131 s，还有1个任务
132 s，还有2个任务
133 s，还有2个任务
134 s，还有2个任务
135 s，还有2个任务
136 s，还有2个任务
137 s，还有2个任务
138 s，还有2个任务
139 s，还有2个任务
140 s，还有2个任务
141 s，还有2个任务
142 s，还有2个任务
143 s，还有2个任务
144 s，还有2个任务
145 s，还有2个任务
146 s，还有2个任务
147 s，还有2个任务
148 s，还有2个任务
149 s，还有2个任务
150 s，还有2个任务
151 s，还有2个任务
152 s，还有2个任务
153 s，还有2个任务
154 s，还有2个任务
155 s，还有2个任务
156 s，还有2个任务
157 s，还有2个任务
158 s，还有2个任务
159 s，还有2个任务
160 s，还有2个任务
161 s，还有2个任务
162 s，还有2个任务
163 s，还有2个任务
164 s，还有1个任务
165 s，还有1个任务
166 s，还有1个任务
167 s，还有1个任务
168 s，还有1个任务
169 s，还有1个任务
170 s，还有1个任务
171 s，还有1个任务
172 s，还有1个任务
173 s，还有1个任务
174 s，还有1个任务
175 s，还有1个任务
176 s，还有2个任务
177 s，还有2个任务
178 s，还有2个任务
179 s，还有2个任务
180 s，还有2个任务
181 s，还有2个任务
182 s，还有2个任务
183 s，还有2个任务
184 s，还有2个任务
185 s，还有2个任务
186 s，还有2个任务
187 s，还有2个任务
188 s，还有2个任务
189 s，还有2个任务
190 s，还有2个任务
191 s，还有2个任务
192 s，还有2个任务
193 s，还有2个任务
194 s，还有2个任务
195 s，还有2个任务
196 s，还有2个任务
197 s，还有2个任务
198 s，还有2个任务
199 s，还有2个任务
200 s，还有2个任务
201 s，还有2个任务
202 s，还有2个任务
203 s，还有2个任务
204 s，还有2个任务
205 s，还有3个任务
206 s，还有3个任务
207 s，还有3个任务
208 s，还有3个任务
209 s，还有3个任务
210 s，还有3个任务
211 s，还有3个任务
212 s，还有3个任务
213 s，还有3个任务
214 s，还有3个任务
215 s，还有3个任务
216 s，还有3个任务
217 s，还有3个任务
218 s，还有3个任务
219 s，还有3个任务
220 s，还有3个任务
221 s，还有3个任务
222 s，还有3个任务
223 s，还有3个任务
224 s，还有3个任务
225 s，还有3个任务
226 s，还有3个任务
227 s，还有3个任务
228 s，还有3个任务
229 s，还有3个任务
230 s，还有3个任务
231 s，还有3个任务
232 s，还有3个任务
233 s，还有3个任务
234 s，还有3个任务
235 s，还有3个任务
236 s，还有3个任务
237 s，还有3个任务
238 s，还有3个任务
239 s，还有3个任务
240 s，还有2个任务
241 s，还有2个任务
242 s，还有2个任务
243 s，还有2个任务
244 s，还有2个任务
245 s，还有2个任务
246 s，还有2个任务
247 s，还有2个任务
248 s，还有2个任务
249 s，还有2个任务
250 s，还有2个任务
251 s，还有2个任务
252 s，还有2个任务
253 s，还有2个任务
254 s，还有2个任务
255 s，还有2个任务
256 s，还有2个任务
257 s，还有2个任务
258 s，还有2个任务
259 s，还有2个任务
260 s，还有2个任务
261 s，还有2个任务
262 s，还有2个任务
263 s，还有2个任务
264 s，还有2个任务
265 s，还有2个任务
266 s，还有2个任务
267 s，还有2个任务
268 s，还有1个任务
269 s，还有1个任务
270 s，还有1个任务
271 s，还有1个任务
272 s，还有1个任务
273 s，还有1个任务
274 s，还有1个任务
275 s，还有1个任务
276 s，还有1个任务
277 s，还有1个任务
278 s，还有1个任务
279 s，还有1个任务
280 s，还有1个任务
281 s，还有1个任务
282 s，还有1个任务
283 s，还有1个任务
284 s，还有1个任务
285 s，还有1个任务
286 s，还有1个任务
287 s，还有1个任务
288 s，还有1个任务
289 s，还有1个任务
290 s，还有1个任务
291 s，还有1个任务
448 s，还有1个任务
449 s，还有1个任务
450 s，还有1个任务
451 s，还有1个任务
452 s，还有1个任务
453 s，还有1个任务
454 s，还有1个任务
455 s，还有1个任务
456 s，还有1个任务
457 s，还有1个任务
458 s，还有1个任务
459 s，还有1个任务
460 s，还有1个任务
461 s，还有1个任务
462 s，还有1个任务
463 s，还有1个任务
464 s，还有2个任务
465 s，还有2个任务
466 s，还有2个任务
467 s，还有2个任务
468 s，还有2个任务
469 s，还有2个任务
470 s，还有2个任务
471 s，还有2个任务
472 s，还有2个任务
473 s，还有2个任务
474 s，还有2个任务
475 s，还有2个任务
476 s，还有2个任务
477 s，还有2个任务
478 s，还有1个任务
479 s，还有1个任务
480 s，还有1个任务
481 s，还有1个任务
482 s，还有1个任务
483 s，还有1个任务
484 s，还有1个任务
485 s，还有1个任务
486 s，还有1个任务
487 s，还有1个任务
488 s，还有1个任务
489 s，还有1个任务
490 s，还有1个任务
491 s，还有1个任务
492 s，还有1个任务
493 s，还有1个任务
494 s，还有1个任务
495 s，还有1个任务
496 s，还有1个任务
497 s，还有1个任务
498 s，还有1个任务
499 s，还有1个任务
平均等待时间 40.56 s，还剩 1 个任务
双端队列——回文词
队首队尾都可以加入或者移除
# 懒得实现了，直接用list操作
队首：x.pop(0) x.insert(0,new)
队尾: x.pop() x.append(new)
size: len(x)
是否为空：x==[]
# 回文词判定
def ishuiwen(string):
string = list(string)
stillhuiwen = True
while len(string) > 1 and stillhuiwen:
tou = string.pop(0)
wei = string.pop()
if tou!=wei: stillhuiwen = False
return(stillhuiwen)
# 测试
ishuiwen("上海自来水来自海上")
ishuiwen("上海自来水不来自海上")
ishuiwen("上海自来水水来自海上")
True
False
True
链表
无序
数据项存放位置没有规则，在数据项之间建立链接指向，就可以保持其前后相对位置，第一个和最后一个需要显示标记出来。
1. 节点Node
- 节点至少包括两个信息：数据本身&指向下一个节点的引用信息
- data + next
- 无序表本身不包含数据项，它包含的head只是对第一个节点的引用。
- 判断isEmpty很容易，self.head是不是none即可
## node实现
class Node:
def __init__(self,initdata):
self.data = initdata # 数据项
self.next = None # 指向
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = new.data
def setNext(self,newnext):
self.next = newnext
## 链表实现
class Unorderedlist: # 只需要一个引用第一个节点的head
def __init__(self):
self.head = None
## 使用
lian = Unorderedlist()
node1 = Node("第一个数据")
node2 = Node("第二个数据")
lian.head = node1
lian.head.setNext(node2)
lian.head.getData() ,lian.head.getNext().getData() # 第二个节点的数据项
('第一个数据', '第二个数据')
2. add
最快捷的——在表头添加，次序时倒过来的
3. size
从head开始遍历，累加经过的节点个数（不是none就+1）
- 链式存储求size要走循环，o(n)
- 顺序存储求size，拿最后一项地址-第一项地址，复杂度o1
4. search
从head开始遍历，判断当前节点数据项是否为目标
5.remove
首先遍历查找，然后删除，删除是把前一个节点的next指向当前的下一个节点（跳过当前）。所以遍历过程中需要保留当前的前一个节点，即不断更新（previous,current)。
双链表：每个节点有数据项本身+previous+next
## 实现
lian = Unorderedlist()
node1 = Node("第一个数据")
node2 = Node("第二个数据")
lian.head = node1
lian.head.setNext(node2)
lian.head.getData() ,lian.head.getNext().getData() # 第二个节点的数据项
##### 1.add
def add(self, item): # 添加在表头
tmp = Node(item) # 根据当前数据项生成新节点
tmp.setNext(self.head) # 新节点的指向原本的head
self.head = tmp # 把当前head替换成新节点
# 使用add加上一个
add(lian, "新加的第一个数据")
lian.head.getData(),lian.head.getNext().getData(),lian.head.getNext().getNext().getData()
######2.size
def size(self):
counter = 0
tmp = self.head
while tmp!=None: # 指向不是none
tmp = tmp.getNext() # 就跳到下一个
counter+=1 # 并且计数+1
return counter
# 测试
size(lian)
######3.search
def search(self, item):
tmp = self.head
match = False
while (tmp!=None) and (not match):
if tmp.getData()==item:
match = True
else:
tmp = tmp.getNext()
return match
# 测试
print("是否包含“第三个数据”：{} \n是否包含“第二个数据”：{}".format(search(lian,'第三个数据'),search(lian,'第二个数据')))
#####4.remove
def remove(self,item):
found = False
current = self.head
previous = None
while not found:
if current.getData() == item:
found==True
else:
previous = current # 一个迭代的思路
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
('第一个数据', '第二个数据')
('新加的第一个数据', '第一个数据', '第二个数据')
3
是否包含“第三个数据”：False
是否包含“第二个数据”：True
有序
- 数据项的相对位置取决于大小，“大小”判定方式可以自己定义
- 采用链表的方式实现，但是 区别在于search 和 add
- search：当数据项大于item时候，可以stop了，直接返回F
- add：需要维护有序性，找到第一个比item大的项，插到前面，需要previous+current，不断更新。
# 实现下有序表的add:
def add(self, item):
current = self.head
previous = None
stop = False
while current!=None and (not stop):
if current.getData()>item:
stop = True
else:
previous = current
current = current.getNext()
newnode = Node(item)
if previous == None:
newnode.setNext(self.head)
self.head = newnode
else:
newnode.setNext(current)
previous.setNext(newnode)
# 测试
class Orderedlist: # 只需要一个引用第一个节点的head
def __init__(self):
self.head = None
youxu = Orderedlist()
node1 = Node(3)
youxu.head = node1
add(youxu,1)
add(youxu,5)
youxu.head.getData(),youxu.head.getNext().getData(), youxu.head.getNext().getNext().getData()
(1, 3, 5)
链表复杂度的总结
- size、search、remove、有序表add——遍历 o(n)
- isEmpty、无序表add ——o(1)
list
基于顺序存储，并优化了
不太熟悉的：
remove(item) 查找并删除某个item
search(item) 查找item，返回bool值
index(item) 查找item，返回索引值
总结
| name | 特点 | 基本操作 |
|---|---|---|
| 栈 | 后进先出 | push, pop, isEmpty |
| 队列 | 先进先出 | enqueue, dequeue, isEmpty |
| 双端队列 | 两头进出 | |
| 链表 | 自由进出，保持相对位置，不需要连续的存储空间 |
练习题目——基数排序：
- 题目内容：
实现一个基数排序算法，用于10进制的正整数从小到大的排序。
思路是保持10个队列(队列0、队列1......队列9、队列main)，
开始，所有的数都在main队列，没有排序。
第一趟将所有的数根据其10进制个位(09)，放入相应的队列09，全放好后，按照FIFO的顺序，将每个队列的数合并排到main队列。
第二趟再从main队列队首取数，根据其十位的数值，放入相应队列0~9，全放好后，仍然按照FIFO的顺序，将每个队列的数合并排到main队列。
第三趟放百位，再合并；第四趟放千位，再合并。
直到最多的位数放完，合并完，这样main队列里就是排好序的数列了。
- 输入格式:
一个列表mylist，其中mylist包含一些需要排序的正整数，正整数互不相同且均不超过100000，且个数在1至1000之间。
- 输出格式：
一个与mylist等长的列表。
a = [8, 91, 341, 22, 65, 381,109,1000, 4, 55, 18,77,225,343,6]
temp=[]
main = a # 最开始所有元素都在main
maxlen = len(str(max(a))) # 最大位数
for i in range(10): # 先预备10维数组，分别准备存0~9
temp.append([])
for j in range(maxlen): # 每一次循环都把j位的数字排序好
while main!=[]:
num = main.pop() # 取出main队列的最后一位，并从main中删除
i = num//(10**j)%10 # 取出对应位数的数字
temp[i].append(num) # 根据对应位数的数字，填入
for i in range(10): # 按照某位上的数字大小排序
while temp[i]!=[]: # j位上等于i，就加入main
main.append(temp[i].pop()) # 顺便清空mylist，准备下一位数
print(j+1, main)
1 [1000, 91, 341, 381, 22, 343, 4, 65, 55, 225, 6, 77, 8, 18, 109]
2 [1000, 4, 6, 8, 109, 18, 22, 225, 341, 343, 55, 65, 77, 381, 91]
3 [1000, 4, 6, 8, 18, 22, 55, 65, 77, 91, 109, 225, 341, 343, 381]
4 [4, 6, 8, 18, 22, 55, 65, 77, 91, 109, 225, 341, 343, 381, 1000]