python 写的一个插入排序，另附 ARM 代码

haishi

好久没写算法什么的，竟然生疏了，多多练习下。

#!/usr/bin/env python
# coding:utf8
class InsertSort(object):
data = [21, 32, 12, 54, 6, 9, 22, 11, 42, 31]
def sort(self):
for i in range(1, len(self.data)):
for j in range(i, 0, -1):
if self.data[j] >= self.data[j - 1]:
break
else:
tmp = self.data[j]
self.data[j] = self.data[j - 1]
self.data[j - 1] = tmp

@staticmethod
def main():
insertSort = InsertSort()
print 'before sorting...'
print insertSort.data
insertSort.sort()
print
print 'after sorting...'
print insertSort.data
if __name__ == '__main__':
InsertSort.main()


ARM 代码就是这次作业了，

area text, code, readonly
num equ 20 * 4          ; numbers to be sort
entry           ; insert sort
start
ldr r0, =src    ; data to be sort
mov r2, #num
sort
mov r3, #4      ; for i in range(1, len(self.data)):
sort_s
cmp r3, r2
BMI for_one
swi 11
for_one
mov r4, r3      ; for j in range(i, 0, -1):
for_one_s
add r4, r4, r0
ldr r5, [r4]
sub r4, r4, #4
ldr r6, [r4]
cmp r5, r6      ; if self.data[j] >= self.data[j - 1]:
strmi r5, [r4]
strmi r6, [r4, #4]
subs r4, r4, r0
beq return_sort ; break
b for_one_s     ; else: continue
return_sort
add r3, r3, #4
b sort_s   

area mydata, data, readwrite
src dcd 1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4
end
对照着 python 代码写汇编的代码就很简单了。
中间调试的时候由于 subs r4, r4, r0
sub 后面的 s 忘了，运行的时候就不影响 CPSR 导致后面的判断失效。


参考：http://zh.wikipedia.org/zh/插入排序