胡一刀的博客

堆排序汇编版- -

                                      

鉴于堆排序的算法时间复杂度和空间复杂度都非常好，写了一个汇编版的。代码如下

;堆排序实现50个数顺存储
;********************************************
;stack   segment para stack 'stack'

;        db      1024 dup (?)
;stack   ends

data    segment para 'data'
          org 1000h
data_buf  db  47,49,48,50,46,45,44,43,42,41
          db  40,39,38,37,36,35,34,33,32,31
          db  30,29,28,27,26,25,24,23,22,21
          db  20,19,18,17,16,15,14,13,12,11
          db  10, 9, 8, 7, 6, 5, 4, 3, 1, 2
msg1      db  'Raw Data:', 0dh,0ah
msg2      db  5 dup(10 dup(?,?,20h,20h),0dh,0ah)
msg3      db  'Sorted Data:', 0dh, 0ah
msg4      db  5 dup(10 dup(?,?,20h,20h),0dh,0ah),'$'

data    ends
;****************************************
program segment
;****************************************

main proc far
   assume cs:program,ds:data
start:
;****************************************
push ds
sub ax,ax
push ax
;*****************************************
mov ax,data
mov ds,ax
;*****************************************
call change1
mov cx,25
mov si,24
mov bx,49       ;初始化

jiandui:
push si                
call sift
pop si
dec si
loop jiandui     ;以上建堆过程，以下调整堆

mov cx,49
mov si,0
mov bx,48
tiaozhengdui:
mov al,data_buf[si]
mov ah,data_buf[bx][1]
mov data_buf[si],ah
mov data_buf[bx][1],al
push si
call sift
pop si
dec bx
loop tiaozhengdui

mov al,data_buf[si]
mov ah,data_buf[1]
mov data_buf[si],ah
mov data_buf[1],al

call change2

;以下将结果显示在屏幕上
mov ah,9
mov dx,seg msg1
mov ds,dx
mov dx,offset msg1
int 21h
ret

main endp

sift proc near      ;以si为根调整堆

continue3:
mov ax,si
add si,si
mov dl,data_buf[si][1]
mov si,ax

mov ax,si
add al,al
add al,2
cmp al,bl    
jnbe continue           ;判断data_buf[2*si][2]是否超出比较范围即没有右子树

mov ax,si
add si,si
cmp dl,data_buf[si][2]
mov si,ax

jge continue
mov ax,si
add si,si
mov dl,data_buf[si][2]
mov si,ax
cmp data_buf[si],dl
jge continue4
xchg dl,data_buf[si]
mov ax,si
add si,si
mov data_buf[si][2],dl
mov si,ax
add si,1
add si,si
jmp continue2

continue:
cmp data_buf[si],dl
jge continue4
xchg dl,data_buf[si]
mov ax,si
add si,si
mov data_buf[si][1],dl
mov si,ax
add si,si
add si,1

continue2:
mov ax,si
add si,si
add si,1
cmp si,bx
mov si,ax
jbe continue3
continue4:
ret
sift endp

change1 proc near
mov bx,0
mov cx,50
next1:
mov al,data_buf[bx]
mov ah,0
mov dl,10
div dl
add al,30h
add ah,30h
push bx
add bx,bx
add bx,bx
cmp bx,40
jge L1
mov msg2[bx],al
mov msg2[bx][1],ah
jmp X
L1:
cmp bx,80
jge L2
mov msg2[bx][2],al
mov msg2[bx][3],ah
jmp X
L2:
cmp bx,120
jge L3
mov msg2[bx][4],al
mov msg2[bx][5],ah
jmp X
L3:
cmp bx,160
jge L4
mov msg2[bx][6],al
mov msg2[bx][7],ah
jmp X
L4:
mov msg2[bx][8],al
mov msg2[bx][9],ah
X:
pop bx
add bx,1
loop next1
ret
change1 endp

change2 proc near
mov bx,0
mov cx,50
next2:
mov al,data_buf[bx]
mov ah,0
mov dl,10
div dl
add al,30h
add ah,30h
push bx
add bx,bx
add bx,bx

cmp bx,40
jge L5
mov msg4[bx],al
mov msg4[bx][1],ah
jmp Y
L5:
cmp bx,80
jge L6
mov msg4[bx][2],al
mov msg4[bx][3],ah
jmp Y
L6:
cmp bx,120
jge L7
mov msg4[bx][4],al
mov msg4[bx][5],ah
jmp Y
L7:
cmp bx,160
jge L8
mov msg4[bx][6],al
mov msg4[bx][7],ah
jmp Y
L8:
mov msg4[bx][8],al
mov msg4[bx][9],ah
Y:

pop bx
add bx,1
loop next2
ret
change2 endp

program ends
    end start

- 作者： hlq83 2005年06月11日, 星期六 16:32 加入博采