msort.asm

单片机程序设计基础 随书光盘

;三字节浮点数归并排序算法。
ADDR	EQU	20H	;三字节浮点数数组起始页面。
TEMP	EQU	28H	;归并排序缓冲区起始页面。
NUMB	EQU	0120H	;浮点数总个数。
D1	EQU	30H	;浮点数暂存器1首址。
D2	EQU	33H	;浮点数暂存器2首址。
NH	DATA	36H	;尚未归并浮点数个数存放单元（高字节）。
NL	DATA	37H	;尚未归并浮点数个数存放单元（低字节）。
LENH	DATA	38H	;子列长度存放单元（高字节）。
LENL	DATA	39H	;子列长度存放单元（低字节）。
CONH	DATA	3AH	;双字节计数器存放单元（高字节）。
CONL	DATA	3BH	;双字节计数器存放单元（低字节）。

	ORG	0000H
	LJMP	TEST
	
	ORG	0100H
TEST:	MOV	P2,#ADDR;将测试数据传送到片外RAM中。
	MOV	R0,#0
	MOV	R2,#HIGH(NUMB)
	MOV	R3,#LOW(NUMB)
	MOV	DPTR,#LIST
	MOV	A,R3
	JZ	TEST1
	INC	R2
TEST1:	MOV	R4,#3
TEST2:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	CJNE	R0,#0,TEST3
	INC	P2
TEST3:	DJNZ	R4,TEST2
	DJNZ	R3,TEST1
	DJNZ	R2,TEST1
	LCALL	MSORT	;调用归并排序算法。
STOP:	LJMP	STOP

MSORT:	MOV	LENH,#0	;初始化子列长度为1个数据元素。
	MOV	LENL,#1
LOOP:	MOV	R2,#ADDR;从原列，
	MOV	DPH,#TEMP;到新列，
	LCALL	MPASS	;调用一轮归并算法。
	MOV	R2,#TEMP;从新列，
	MOV	DPH,#ADDR;到原列，
	LCALL	MPASS	;再调用一轮归并算法，使结果保存在原列中。
	MOV	A,LENL	;取下一轮子列长度。
	CLR	C
	SUBB	A,#LOW(NUMB);和待排序数据总数相比。
	MOV	A,LENH
	SUBB	A,#HIGH(NUMB)
	JC	LOOP	;未覆盖全部数据元素，继续归并。
LOOPE:	RET		;已覆盖全部数据元素，归并结束。

MPASS:	MOV	NH,#HIGH(NUMB);一轮归并算法，初始化全部元素均未处理。
	MOV	NL,#LOW(NUMB)
	MOV	R0,#0	;初始化左子列指针（R2R0）。
	MOV	DPL,#0	;初始化目标列指针（DPTR）。
MERGS:	MOV	A,NH	;取尚未处理元素个数。
	ORL	A,NL
	JZ	MERGSE	;没有未处理元素，该轮归并结束。
	MOV	A,NL	;从中截取一个子列，作为左子列。
	CLR	C
	SUBB	A,LENL
	MOV	B,A
	MOV	A,NH
	SUBB	A,LENH
	JNC	MERGS2	;可以截取到一个完整的左子列。
MERGS1:	MOV	A,R0	;左子列不够一个完整子列的长度时，
	MOV	R1,A	;直接转抄到目标列。
	MOV	P2,R2	;取指针高字节。
	MOV	CONH,NH	;将全部剩余元素，
	MOV	CONL,NL	;作为转抄对象。
	LCALL	MOVS	;进行转抄。
MERGSE:	MOV	A,LENL	;将该轮归并算法的子列长度加倍。
	CLR	C
	RLC	A
	MOV	LENL,A	;作为下一轮归并算法的子列长度。
	MOV	A,LENH
	RLC	A
	MOV	LENH,A
	RET		;结束本轮归并算法。
MERGS2:	MOV	NH,A
	ORL	A,B
	JZ	MERGS1	;刚好够一个完整的左子列，进行转抄。
	MOV	NL,B	;保存截取一个完整的左子列后的剩余元素个数。
	MOV	R4,LENH	;左子列长度（R4R5）为指定长度。
	MOV	R5,LENL
	MOV	A,R5	;计算左子列字节数。
	MOV	B,#3
	MUL	AB
	MOV	R6,B
	MOV	R7,A
	MOV	A,R4
	MOV	B,#3
	MUL	AB
	ADD	A,R6
	MOV	R6,A	
	MOV	A,R0	;取左子列起始地址（R2R0），
	ADD	A,R7	;加上左子列字节数（暂存于R6R7），
	MOV	R1,A	;得到右子列起始地址（R3R1）。
	MOV	A,R2
	ADDC	A,R6
	MOV	R3,A
	MOV	A,NL	;取截取一个完整的左子列后的剩余元素个数。
	CLR	C
	SUBB	A,LENL	;从中再截取一个子列，作为右子列。
	MOV	B,A
	MOV	A,NH
	SUBB	A,LENH
	JNC	MERGS3	;能够截取到一个完整的右子列。
	MOV	R6,NH	;不能截取到一个完整的右子列，将全部剩余元素，
	MOV	R7,NL	;作为右子列的长度（R6R7）。
	MOV	NH,#0	;再没有剩余元素了。
	MOV	NL,#0
	SJMP	MERGS4	;准备进行归并操作。
MERGS3:	MOV	NH,A	;保存截取右子列后的剩余元素个数。
	MOV	NL,B
	MOV	R6,LENH	;一个完整的右子列。
	MOV	R7,LENL
MERGS4:	MOV	A,R7	;计算下一次归并操作的左子列首址，保存之。
	MOV	B,#3
	MUL	AB
	MOV	CONH,B
	MOV	CONL,A
	MOV	A,R6
	MOV	B,#3
	MUL	AB
	ADD	A,CONH
	MOV	CONH,A	
	MOV	A,R1
	ADD	A,CONL
	PUSH	ACC
	MOV	A,R3
	ADDC	A,CONH
	PUSH	ACC
	LCALL	MERGE	;调用将两个有序子列进行归并的算法。
	POP	ACC	;调整左子列首址，
	MOV	R2,A
	POP	ACC
	MOV	R0,A
	LJMP	MERGS	;继续进行下一次归并操作。

MERGE:	MOV	A,R0	;从左子列和右子列各取一个元素。
	PUSH	ACC
	XCH	A,R1
	PUSH	ACC
	MOV	R0,#D1
	MOV	P2,R2
	LCALL	LOAD
	POP	ACC
	PUSH	ACC
	MOV	R1,A
	MOV	P2,R3
	MOV	R0,#D2
	LCALL	LOAD
	MOV	R0,#D1
	MOV	R1,#D2
	LCALL	FCMP	;比较浮点数的大小（参阅浮点子程序库）。
	POP	ACC
	MOV	R1,A
	POP	ACC
	MOV	R0,A
	JC	MERG5	;左小。	
	MOV	P2,R3	;取右子列元素，转抄到目标列。
	MOV	B,#3	;一个元素三个字节。
MERG2:	MOVX	A,@R1
	MOVX	@DPTR,A
	INC	DPTR
	INC	R1
	CJNE	R1,#0,MERG3
	INC	P2
	INC	R3
MERG3:	DJNZ	B,MERG2
	CJNE	R7,#0,MERG4;右子列元素减少一个。
	DEC	R6
MERG4:	DEC	R7
	MOV	A,R6
	ORL	A,R7
	JNZ	MERGE	;右子列元素若未全部处理完毕，则继续归并。
	MOV	A,R0	;右子列全部处理完毕，准备转抄左子列剩余元素。
	MOV	R1,A
	MOV	P2,R2
	MOV	CONH,R4	;取左子列剩余元素个数，
	MOV	CONL,R5	;控制转抄元素个数。
	SJMP	MOVS	;进行转抄，结束这次归并操作。
MERG5:	MOV	P2,R2	;取左子列元素，转抄到目标列。
	MOV	B,#3	;一个元素三个字节。
MERG6:	MOVX	A,@R0
	MOVX	@DPTR,A
	INC	DPTR
	INC	R0
	CJNE	R0,#0,MERG7
	INC	P2
	INC	R2
MERG7:	DJNZ	B,MERG6
	CJNE	R5,#0,MERG8;左子列元素减少一个。
	DEC	R4
MERG8:	DEC	R5
	MOV	A,R4
	ORL	A,R5
	JNZ	MERGE	;左子列元素若未全部处理完毕，则继续归并。
	MOV	P2,R3	;左子列全部处理完毕，准备转抄右子列剩余元素。
	MOV	CONH,R6	;取右子列剩余元素个数，
	MOV	CONL,R7	;控制转抄元素个数。
MOVS:	MOV	A,CONL
	JZ	MOVS1
	INC	CONH
MOVS1:	MOV	B,#3
MOVS2:	MOVX	A,@R1	;进行转抄。
	MOVX	@DPTR,A
	INC	DPTR
	INC	R1
	CJNE	R1,#0,MOVS3
	INC	P2
MOVS3:	DJNZ	B,MOVS2
	DJNZ	CONL,MOVS1
	DJNZ	CONH,MOVS1
	RET	;将指定数目的元素转抄完毕。

LOAD:	MOV	B,#3	;将一个元素调入片内。
LOAD1:	MOVX	A,@R1
	MOV	@R0,A
	INC	R0
	INC	R1
	CJNE	R1,#0,LOAD2
	INC	P2
LOAD2:	DJNZ	B,LOAD1
	RET

FCMP:	MOV	A,@R0		;比较两个浮点数的大小。
	XRL	A,@R1
	JNB	ACC.7,CMP2
	MOV	A,@R0
	RLC	A
	MOV	A,#0FFH
	RET
CMP2:	MOV	A,@R1
	MOV	C,ACC.6
	MOV	ACC.7,C
	MOV	B,A
	MOV	A,@R0
	MOV	C,ACC.7
	MOV	F0,C
	MOV	C,ACC.6
	MOV	ACC.7,C
	CLR	C
	SUBB	A,B
	JZ	CMP6
	RLC	A
	JNB	F0,CMP5
	CPL	C
CMP5:	MOV	A,#0FFH
	RET
CMP6:	INC	R0
	INC	R0
	INC	R1
	INC	R1
	CLR	C
	MOV	A,@R0
	SUBB	A,@R1
	MOV	B,A	
	DEC	R0
	DEC	R1
	MOV	A,@R0
	SUBB	A,@R1
	DEC	R0
	DEC	R1
	ORL	A,B
	JZ	CMP7
	JNB	F0,CMP7
	CPL	C
CMP7:	RET
LIST:	DB	0BH,94H,0A7H,0F3H,94H,0EBH	;288个浮点测试数据。
	DB	78H,9DH,66H,7AH,0ACH,0C8H
	DB	7AH,99H,03H,8EH,0A0H,66H
	DB	76H,8CH,0D5H,8CH,9AH,0B0H
	DB	00H,0D6H,1EH,76H,0C3H,0D2H
	DB	7DH,0FAH,5AH,0BH,0CBH,55H
	DB	0F1H,0EAH,0BCH,0DH,0D7H,9CH
	DB	85H,0F3H,9AH,75H,0F3H,50H
	DB	0FBH,0EAH,0AH,0F9H,0C1H,5AH
	DB	89H,0ABH,4AH,05H,0E9H,4DH
	DB	80H,0A9H,0ACH,85H,0B5H,9EH
	DB	84H,0B3H,0D6H,0F4H,0FAH,0D8H
	DB	0FAH,0DBH,0FH,0F9H,0E1H,0E6H
	DB	7DH,0BCH,0DEH,8DH,9BH,0D8H
	DB	0F0H,0FBH,0DH,7EH,0E1H,0A5H
	DB	0FDH,0B4H,0B9H,8DH,97H,37H
	DB	0F0H,0E6H,0F7H,7AH,0DEH,0F9H
	DB	8BH,0DFH,28H,73H,0E5H,1FH
	DB	7FH,0A3H,0EEH,8FH,0FDH,0C4H
	DB	82H,0B8H,9FH,0F1H,93H,0E5H
	DB	0FEH,0FCH,0BEH,7CH,97H,0D1H
	DB	0F9H,0FAH,33H,7EH,0C6H,6FH
	DB	0FBH,0CDH,0F2H,0DH,0BEH,57H
	DB	03H,0CAH,0E2H,0F6H,0DCH,43H
	DB	0FH,88H,72H,75H,8EH,59H
	DB	0EH,0CBH,20H,04H,0E4H,1BH
	DB	07H,83H,7BH,85H,0EFH,74H
	DB	02H,0EEH,9CH,81H,0D3H,80H
	DB	87H,0F0H,1EH,77H,83H,0C6H
	DB	0F9H,0F8H,0D3H,08H,9AH,79H
	DB	0F1H,0CFH,3BH,7CH,0E7H,75H
	DB	0DH,0EEH,0AFH,87H,0D5H,0F2H
	DB	83H,0BEH,5DH,77H,0CBH,0BCH
	DB	0FAH,0F7H,8BH,0FH,0F1H,79H
	DB	0F5H,0AFH,30H,0FBH,0E6H,06H
	DB	88H,0C0H,0CEH,87H,99H,0D5H
	DB	03H,0BAH,0B8H,70H,0D7H,19H
	DB	0FCH,0E3H,30H,7DH,0E6H,19H
	DB	8BH,0C3H,27H,81H,0E4H,0FBH
	DB	03H,9FH,66H,81H,0ECH,0C7H
	DB	72H,98H,0FDH,8FH,9FH,0ADH
	DB	76H,0F5H,0B7H,7CH,0B6H,0E7H
	DB	0FFH,0DCH,0E6H,0FAH,9CH,0D7H
	DB	7BH,9AH,0E6H,7EH,0DCH,0DAH
	DB	7EH,9BH,49H,7DH,0E9H,3BH
	DB	7EH,0A7H,61H,8DH,0ECH,2EH
	DB	84H,85H,0CEH,83H,0B9H,0D9H
	DB	06H,0BBH,20H,0F2H,0E4H,0FH
	DB	0FCH,81H,0F2H,8DH,0BEH,4BH
	DB	02H,0C9H,73H,0F0H,0AEH,79H
	DB	0FH,0CFH,3EH,84H,0E7H,0D5H
	DB	07H,0FAH,0BFH,87H,0D7H,0F0H
	DB	0F3H,0FEH,19H,7DH,0C3H,3CH
	DB	0FBH,0E7H,90H,0FH,0F2H,07H
	DB	81H,0C0H,0FAH,0F3H,9FH,57H
	DB	09H,0EAH,0E1H,70H,0DCH,2FH
	DB	8FH,85H,0F8H,75H,0BFH,0EH
	DB	0EH,0E1H,0D6H,0F2H,0BAH,0D9H
	DB	8FH,0DBH,34H,0F0H,0E6H,9BH
	DB	7DH,0D3H,7FH,8DH,0EFH,0FDH
	DB	73H,0FFH,0B4H,89H,0F6H,9BH
	DB	0F7H,0D3H,70H,0FFH,0EEH,0CH
	DB	7BH,0C1H,98H,89H,0B3H,1EH
	DB	07H,0E3H,0D6H,0F0H,0FAH,0C9H
	DB	89H,0D9H,3BH,0F1H,0A7H,63H
	DB	7DH,0ECH,76H,8CH,8EH,0C5H
	DB	83H,0D8H,0B7H,06H,96H,0FAH
	DB	77H,0DFH,51H,7CH,0EAH,34H
	DB	7BH,0C6H,9EH,8FH,0D3H,0CAH
	DB	05H,0F9H,49H,73H,0A9H,20H
	DB	0F9H,0A4H,09H,8CH,81H,2DH
	DB	84H,0A5H,0A6H,02H,0B4H,0C5H
	DB	80H,98H,0B3H,0F2H,96H,70H
	DB	7AH,0CEH,0EH,7CH,0C1H,0DEH
	DB	0BH,0BBH,0D2H,07H,0FAH,4BH
	DB	0F0H,0C9H,70H,0FDH,0AEH,04H
	DB	0DH,0C0H,8EH,84H,91H,0CDH
	DB	07H,0B9H,0AAH,70H,0B5H,54H
	DB	0F8H,0AAH,8AH,0FCH,0D1H,4CH
	DB	8AH,0A9H,9BH,75H,0B3H,79H
	DB	88H,0EFH,39H,0F4H,0E7H,38H
	DB	89H,0E7H,00H,87H,0E0H,0EH
	DB	83H,81H,0DCH,83H,0BBH,90H
	DB	00H,0F2H,03H,0F0H,0C0H,61H
	DB	0FDH,8CH,38H,09H,87H,12H
	DB	00H,0E2H,54H,06H,0CAH,9FH
	DB	83H,0D3H,0FAH,01H,0FFH,46H
	DB	75H,0E8H,0C5H,0F9H,98H,0B6H
	DB	8FH,96H,0DCH,74H,0DBH,8FH
	DB	7CH,0F1H,0E4H,7BH,0BCH,80H
	DB	0FDH,90H,0BH,0F8H,81H,7EH
	DB	7EH,0AFH,0D4H,08H,0FAH,88H
	DB	80H,0D1H,18H,0F7H,0A3H,0EH
	DB	7DH,0E1H,0C9H,88H,0B9H,39H
	DB	81H,0A7H,39H,0F0H,0E7H,22H
	DB	8CH,0E4H,48H,83H,89H,09H
	DB	83H,0A1H,29H,02H,0A5H,3DH
	DB	84H,0A7H,0A8H,80H,0F5H,1CH
	DB	82H,0A3H,95H,0F3H,0F2H,0B4H
	DB	8AH,0D6H,8EH,0F1H,0D1H,0DEH
	DB	79H,0BBH,0D5H,7BH,0FAH,0ADH
	DB	0F8H,0D5H,0B1H,0FDH,0B6H,2AH
	DB	7DH,0C5H,57H,0FAH,0AAH,0ECH
	DB	0BH,0DDH,85H,82H,0B0H,0B7H
	DB	75H,96H,0F7H,0FEH,0DEH,0ECH
	DB	78H,0DDH,87H,7BH,0B0H,0ECH
	DB	7FH,9DH,9DH,0FEH,0B3H,0AAH
	DB	78H,0F5H,45H,0FEH,0A8H,0ACH
	DB	0F9H,95H,9FH,8AH,0B3H,0E9H
	DB	74H,0FDH,35H,0FAH,0A6H,0A7H
	DB	0F9H,0D4H,0EEH,8EH,9DH,0DDH
	DB	73H,0BBH,0A3H,7AH,0F4H,79H
	DB	0FEH,8FH,24H,0FDH,0E4H,8CH
	DB	0AH,91H,9DH,87H,0B3H,0A1H
	DB	72H,0F4H,37H,0F8H,86H,0F2H
	DB	0F9H,0DEH,52H,0AH,0CAH,56H
	DB	73H,0CAH,0C9H,0FH,0D9H,2EH
	DB	05H,0A5H,0C4H,75H,0B8H,9BH
	DB	8CH,93H,6DH,0F2H,0EDH,0AAH
	DB	7CH,0B5H,47H,89H,0A8H,0E7H
	DB	0F6H,9CH,0EAH,8AH,9DH,59H
	DB	74H,0ABH,33H,7EH,0E6H,7FH
	DB	8EH,0CFH,0F4H,85H,0FEH,98H
	DB	03H,0D3H,06H,0F7H,0E0H,0CBH
	DB	7FH,99H,66H,89H,0ACH,0C1H
	DB	70H,98H,33H,8CH,86H,6DH
	DB	76H,0CDH,0A6H,0CH,0B4H,0D9H
	DB	03H,9BH,2CH,0F6H,0E5H,80H
	DB	7AH,0B0H,05H,8DH,80H,0A7H
	DB	0F2H,94H,0E9H,08H,9DH,20H
	DB	70H,0A4H,14H,7AH,82H,99H
	DB	8EH,0D3H,3BH,02H,0E7H,7BH
	DB	71H,0EFH,7CH,89H,0EFH,86H
	DB	83H,0F0H,0DAH,87H,9BH,4EH
	DB	0F7H,0E9H,0CEH,78H,0B9H,0CBH
	DB	8DH,0B9H,6FH,0F4H,0ADH,0F4H
	DB	0FCH,0BEH,9BH,8CH,0D3H,78H
	DB	0F6H,0EFH,16H,7FH,0E2H,0CFH
	DB	89H,0D9H,0F1H,87H,0BEH,3BH
	DB	71H,0C7H,6AH,0FCH,0EDH,45H
	DB	0FH,0A8H,0A4H,83H,94H,8CH
	DB	86H,91H,84H,74H,0B0H,9AH
	DB	7AH,93H,52H,0F8H,0EAH,58H
	DB	78H,0CBH,05H,89H,0E0H,0A6H
	END