qucksort.asm

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

;快速排序算法。
DATS	EQU	20H	;待排序数据所在页面。
N	EQU	5DH	;单字节数据个数（不超过255个）。
QUEUE	EQU	1FH	;循环队列存储页面。
F	DATA	3CH	;队首指针的存放单元。
R	DATA	3DH	;队尾指针的存放单元。

	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	SETNULL	;初始化队列。
	MOV	A,#0	;待排序数据块首址（低八位）。
	LCALL	DATAIN	;入队。
	MOV	A,#N	;待排序数据个数。
	DEC	A	;减一，得到待排序数据块末址（低八位）。
	LCALL	DATAIN	;入队。
	LCALL	QSORT	;调用快速排序算法。
STOP:	LJMP	STOP	;测试结束。

QSORT:	MOV	A,F	;取队首指针，
	XRL	A,R	;和队尾指针比较。
	JNZ	QUICK0	;不是空队。
QUICKE:	RET		;是空队，排序结束。
QUICK0:	LCALL	DATAOUT	;从队列中出队待排序数据块的首址。
	MOV	R2,A	;暂存。
	MOV	R0,A	;初始化左指针。
	LCALL	DATAOUT	;从队列中出队待排序数据块的末端地址。
	MOV	R3,A	;暂存。
	MOV	R1,A	;初始化右指针。
	MOV	P2,#DATS;指向待排序数据所在页面。
	MOVX	A,@R0	;取左端第一个元素，
	MOV	B,A	;作为基准数，保存之。
	SETB	F0	;准备扫描未定区的右端。
QUICK1:	MOV	A,R0	;取左指针，
	XRL	A,R1	;和右指针比较。
	JZ	QUICK6	;相同，未定区消失，分区操作完成。
	JNB	F0,QUICK4;扫描方向？
	MOVX	A,@R1	;扫描未定区右端，
	CLR	C
	SUBB	A,B	;和基准数比较。
	JC	QUICK2	;小于基准数。
	DEC	R1	;不小于基准数，右指针左移，扩展大数区。
	LJMP	QUICK1	;继续处理。
QUICK2:	MOVX	A,@R1	;将这个小于基准数的元素，
	MOVX	@R0,A	;移到未定区左端的空位里。
	INC	R0	;左指针右移，扩展小数区。
	CLR	F0	;准备扫描未定区左端。
	LJMP	QUICK1	;继续处理。
QUICK4:	MOVX	A,@R0	;扫描未定区左端，
	CLR	C
	SUBB	A,B	;和基准数比较。
	JNC	QUICK5	;不小于基准数。
	INC	R0	;小于基准数，左指针右移，扩展小数区。
	LJMP	QUICK1	;继续处理。
QUICK5:	MOVX	A,@R0	;将这个不小于基准数的元素，
	MOVX	@R1,A	;移到未定区右端的空位里。
	DEC	R1	;右指针左移，扩展大数区。
	SETB	F0	;准备扫描未定区右端。
	LJMP	QUICK1	;继续处理。
QUICK6:	MOV	A,B	;取基准数。
	MOVX	@R0,A	;放入空位中。
	MOV	A,R0	;取空位地址。
	JZ	QUICK7	;小数区不存在。
	DEC	A	;减一，得到小数区末端地址。
	SETB	C
	SUBB	A,R2	;和小数区首址比较。
	JC	QUICK7	;小数区不足两个元素。
	MOV	A,R2	;小数区超过一个元素，取小数区首址。
	LCALL	DATAIN	;入队。
	MOV	A,R0	;取空位地址，
	DEC	A	;减一，得到小数区末端地址。
	LCALL	DATAIN	;入队。
QUICK7:	MOV	A,R3	;取大数区末端地址。
	DEC	A
	SETB	C
	SUBB	A,R1	;和空位地址比较。
	JC	QUICK8	;大数区不足两个元素。
	MOV	A,R1	;取空位地址，
	INC	A	;加一，得到大数区首址。
	LCALL	DATAIN	;入队。
	MOV	A,R3	;取大数区末端地址。
	LCALL	DATAIN	;入队。
QUICK8:	LJMP	QSORT	;继续处理队列中的无序数据块。

SETNULL:MOV	A,#0FFH	;设置空队列。
	MOV	F,A	;使队首指针指向队列页面的最后一个单元。
	MOV	R,A	;使队尾指针也指向队列页面的最后一个单元。
	RET	

DATAIN:	INC	R	;调整队尾指针。
	MOV	DPL,R
	MOV	DPH,#QUEUE
	MOVX	@DPTR,A	;排入队尾。
	RET
	
DATAOUT:INC	F	;调整队首指针。
	MOV	DPL,F
	MOV	DPH,#QUEUE
	MOVX	A,@DPTR	;取待出队数据。
	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