课程设计,题目:1、快速排序,2、折半查找"/>
基于8086CPU的汇编课程设计,题目:1、快速排序,2、折半查找
最近课设在写汇编课程设计,题目也算是不经意间选了两个,并且两个题目之间也有相似部分,实现的方法也是类似的。
2019夏之汇编课程设计,保证代码,注释都开源。若有错误,欢迎指教。
课本:From 王爽老师
题目:快速排序+折半查找
一、快速排序
快速排序大家对算法都很熟悉,用汇编语言来实现主要是解决字符的输入输出,与有限的寄存器的矛盾。采用栈,缓冲区等方法来保存数据,增大保存信息的容量,不失为一种好方法。对于数据区的定义,存入,取出都是对CPU运作原理的理解与应用。
关于快速排序实现的思想,这篇博客给了我很多启发,Thanks,贴:大佬链接,对快拍的理解很深啊。
不只是标准思路,选第一个作为标准,一个方向:从前往后找一个 大于标准值的,找到先暂停,另一个方向,从后往前找一个小于标准值的,将这两个数字交换,如此继续,两个坐标相向而行,直到相遇,相遇后讲标准值和相遇点的值交换,从相遇点将数组看成两段,继续做快拍,所以快拍的时间复杂度为 Nlog2(N),每次都是二分的思想,所以是很快的。
但是假如用汇编实现,所需要的寄存器数量比较多,写起来肯定复杂,寄存器交作。所以采用下面这种两头交换法,二分分段的思想,实现,(两头交换法与标准算法思想的差异是,先从左边开始找到大于基准值的那个数,再从右边找到小于基准值的那个数,将两个数交换(这样比基准值小的都在左边,比基准值大的都在右边)。直到数列分成大于基准值和小于基准值的两个区间,以这两个区间进行同样的排序操作。)
汇编Code如下:
assume cs:code,ds:data
data segmentcount dw 10buffer db 20H dup(?) ; 例: 88,9,00,5,7,3,44,2,44,8; (字节型能保存的最大数值是 0 -- 2^8-1,; 但是为了简化输入和输出,只考虑了0-99,想做三位数后面的注释有提示 )str0 db 0DH,0AH,24H ;回车,换行,结束string db '--please input 10 numbers--',0DH,0AH,'$' ;,0DH,0AH,表示回车换行,'$'表示结束符str1 db '--The 10 numbers Out as --',0DH,0AH,'$' ;,0DH,0AH,表示回车换行,'$'表示结束符
data ends
code segment
start:mov ax,datamov ds,axcall showcall inputmov si,offset buffermov di,offset buffermov bx,offset bufferadd bx,count ;count 代表数据个个数dec bxcall QSORTcall displaymov ah,4CH ;结束int 2
更多推荐
基于8086CPU的汇编课程设计,题目:1、快速排序,2、折半查找
发布评论