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

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

#!/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/插入排序