mergsort.asm

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

;归并排序算法。
DATS	EQU	20H	;待排序数据（原列）所在页面。
N	EQU	5DH	;单字节数据个数（不超过255个）。
DATS1	EQU	21H	;缓冲区（新列）所在页面。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	DPTR,#LIST;将测试数据拷贝到片外RAM中。
	MOV	P2,#DATS
	MOV	R0,#0
	MOV	R2,#N
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	LCALL	MGSORT	;测试归并排序算法。
STOP:	LJMP	STOP	;测试结束。

MGSORT:	MOV	R3,#1	;初始化子列长度为1个数据元素。
LOOP:	MOV	P2,#DATS;从原列，
	MOV	DPH,#DATS1;到新列，
	LCALL	MGPASS	;调用一轮归并算法。
	MOV	P2,#DATS1;从新列，
	MOV	DPH,#DATS;到原列，
	LCALL	MGPASS	;再调用一轮归并算法，使结果保存在原列中。
	JC	LOOPE	;长度超过255个元素，排序结束。
	MOV	A,R3	;取下一轮子列长度。
	CLR	C
	SUBB	A,#N	;和待排序数据总数相比。
	JC	LOOP	;未覆盖全部数据元素，继续归并。
LOOPE:	RET		;已覆盖全部数据元素，归并结束。

MGPASS:	MOV	R7,#N	;一轮归并算法，初始化全部元素均未处理。
	MOV	R0,#0
	MOV	DPL,#0
MERGS:	MOV	A,R7	;取尚未处理元素个数。
	JZ	MERGSE	;没有未处理元素，该轮归并结束。
	CLR	C
	SUBB	A,R3	;从中截取一个子列，作为左子列。
	JNC	MERGS2	;可以截取到一个完整的左子列。
MERGS1:	MOV	A,R0	;左子列不够一个完整子列的长度时，
	MOV	R1,A	;直接转抄到目标列。
	MOV	A,R7	;将全部剩余元素，作为转抄对象。
	MOV	R2,A
	LCALL	MOVS	;进行转抄。
MERGSE:	MOV	A,R3	;将该轮归并算法的子列长度加倍。
	CLR	C
	RLC	A
	MOV	R3,A	;作为下一轮归并算法的子列长度。
	RET		;结束本轮归并算法。
MERGS2:	JZ	MERGS1	;刚好够一个完整的左子列，进行转抄。
	MOV	R7,A	;保存截取一个完整的左子列后的剩余元素个数。
	MOV	A,R3
	MOV	R6,A	;左子列长度为指定长度。
	MOV	A,R0	;取左子列起始地址，
	ADD	A,R3	;加上左子列长度，
	MOV	R1,A	;得到右子列起始地址。
	MOV	A,R7	;取截取一个完整的左子列后的剩余元素个数。
	CLR	C
	SUBB	A,R3	;从中再截取一个子列，作为右子列。
	JNC	MERGS3	;能够截取到一个完整的右子列。
	MOV	A,R7	;否则，将全部剩余元素，作为右子列的长度。
	MOV	R5,A
	MOV	R7,#0	;再没有剩余元素了。
	SJMP	MERGS4	;准备进行归并操作。
MERGS3:	MOV	R7,A	;保存截取右子列后的剩余元素个数。
	MOV	A,R3
	MOV	R5,A	;一个完整的右子列。
MERGS4:	MOV	A,R0	;将当前的左子列起始地址，
	ADD	A,R6	;加上左子列长度，
	ADD	A,R5	;再加上右子列长度，
	MOV	R4,A	;得到下一次归并操作的左子列首址，保存之。
	LCALL	MERGE	;调用将两个有序子列进行归并的算法。
	MOV	A,R4	;调整左子列首址，
	MOV	R0,A
	LJMP	MERGS	;继续进行下一次归并操作。

MERGE:	MOVX	A,@R1	;读取右子列未处理的元素。
	MOV	B,A	;暂存。
	MOVX	A,@R0	;读取左子列未处理的元素。
	CLR	C
	SUBB	A,B	;比较两者大小。
	JC	MERG1	;左小转移。
	MOVX	A,@R1	;右小或相等，取右子列元素，
	MOVX	@DPTR,A	;转抄到目标列。
	INC	R1	;调整右子列指针。
	INC	DPTR	;调整目标指针，指向下一个存放地址。
	DJNZ	R5,MERGE;右子列元素若未全部处理完毕，则继续归并。
	MOV	A,R0	;右子列全部处理完毕，准备转抄左子列剩余元素。
	MOV	R1,A
	MOV	A,R6	;取左子列剩余元素个数，
	MOV	R2,A	;控制转抄元素个数。
	SJMP	MOVS	;进行转抄，结束这次归并操作。
MERG1:	MOVX	A,@R0	;左小，取左子列元素，
	MOVX	@DPTR,A	;转抄到目标列。
	INC	R0	;调整左子列指针。
	INC	DPTR	;调整目标指针，指向下一个存放地址。
	DJNZ	R6,MERGE;左子列元素若未全部处理完毕，则继续归并。
	MOV	A,R5	;左子列全部处理完毕，准备转抄右子列剩余元素。
	MOV	R2,A	;控制转抄元素个数。
MOVS:	MOVX	A,@R1	;进行转抄。
	MOVX	@DPTR,A
	INC	DPTR
	INC	R1
	DJNZ	R2,MOVS
	RET		;将指定数目的元素转抄完毕。

LIST:	DB	70H,90H,1EH,87H	;93个单字节测试数据。
	DB	9FH,0F3H,93H,6BH
	DB	8EH,14H,04H,7FH
	DB	75H,43H,7DH,1AH
	DB	7CH,0FH,0A4H,0CCH
	DB	0BCH,55H,3BH,4EH
	DB	02H,0A5H,3FH,0BFH
	DB	2AH,0B9H,80H,34H
	DB	8CH,0C3H,0D1H,41H
	DB	0A8H,40H,17H,01H
	DB	1BH,4FH,3DH,72H
	DB	0B6H,9DH,4CH,3CH
	DB	0B3H,03H,1CH,66H
	DB	38H,5CH,0C6H,45H
	DB	0E1H,0B0H,0ABH,30H
	DB	5BH,07H,27H,12H
	DB	0D6H,0E7H,60H,63H
	DB	0EH,0C8H,88H,99H
	DB	95H,0A2H,0C0H,5AH
	DB	0D3H,23H,0CAH,0DBH
	DB	79H,58H,5FH,0F5H
	DB	4AH,32H,0DEH,0F2H
	DB	0E3H,0D8H,59H,2FH,31H
	END