assume cs:code
;============================================================================
data segment
array   db 17,5,6,28,-3,0,-18,37,89,-100;待排序序列
line    dw 9;print_num例程 使用，决定第几行输出
message db '   please type 1-4 to chose buble/insert/quick/select sort:',0;print_string的提示消息
wrong   db '   you type the wrong key,press any key to exit (=',0
array_back_up  db 17,5,6,28,-3,0,-18,37,89,-100;每次排序完成后，由此恢复到array
data ends

;============================================================================
stack segment
        db 2048 dup (0)
stack ends
code segment
start:  mov ax,data
        mov ds,ax
        mov ax,stack
        mov ss,ax
        mov sp,256
      
        
        ;清屏幕
        call clear_screen

        ;显示待排序列
        mov dh,2
        call print_num

        ;提示输入
        mov dh,4
        mov si,offset message
        call print_string

@@m5:   ;以下代码用于恢复待排序列原装，以便多次排序
        mov ax,data
        mov es,ax
        mov si,offset array_back_up
        mov di,offset array
        mov cx,10
        cld
        rep movsb

        ;以下恢复 line的行数
        mov line,9

        ;以下代码用于等待输入并选择对应排序算法
        mov ah,0
        int 16h;调用键盘输入中断

        

        call clear_screen;清屏

        ;显示用户输入的ascii
        mov bl,al
        call type_callback

        mov dh,6
        mov si,offset message
        call print_num;显示提示

        ;提示输入
        mov dh,4
        call print_string
        cmp al,'0'
        je @@m0;调用分隔符
        cmp al,'1'
        je @@m1;调用冒泡
        cmp al,'2'
        je @@m2;调用插入
        cmp al,'3'
        je @@m3;调用快排
        cmp al,'4'
        je @@m4;调用选择

        ;显示错误输入
        mov dh,8
        mov si,offset wrong
        call print_string

        ;等待任意输入exit
        mov ah,0
        int 16h
        mov ax,4c00h
        int 21h

@@m0:   mov dh,9
        call print_num_with_spilt
        jmp short @@m5

@@m1:   call buble_sort
        jmp short @@m5

@@m2:   call insert_sort
        jmp short @@m5

@@m3:   mov ax,0
        push ax;传递参数 左边界索引
        mov ax,9
        push ax;传递参数 右边界索引
        call quick_sort
        pop ax
        pop ax
        jmp short @@m5


@@m4:   call select_sort
        jmp short @@m5


 ;============================================================================
 ;清屏例程 无任何参数及返回值       
clear_screen:
        push ax
        push es
        push bx
        push cx
        mov cx,2000
        mov ax,0b800h
        mov es,ax
        mov bx,0
@@c1:   mov byte ptr es:[bx],0
        add bx,2
        loop @@c1
        pop cx
        pop bx
        pop es
        pop ax
        ret

;============================================================================
 ;右下角显示用户按下的键 参数 bl为ascii码，非法输入为'!' 无返回值
 type_callback:
        push ax
        push bx
        push cx
        push es
        
        mov ax,0b800h
        mov es,ax
        mov es:[3990],bl
        mov es:byte ptr [3991],2
        pop es
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
 ;显示提示字符串，参数dh为 行号，列默认为0及返回值   ds:si为字符串首地址     
print_string:
        push ax
        push bx
        push cx
        push dx
        push es
        push si
        push di
        mov ax,0b800h
        mov es,ax
        mov al,160
        mul dh
        mov di,ax
        mov bx,0
@@ps1:   mov al,[si+bx]
        cmp al,0
        je @@ps2
        mov es:[di],al
        inc bx
        add di,2
        loop @@ps1

@@ps2:  pop di 
        pop si
        pop es
        pop dx
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
 ;显示array序列，并以','分割
 ;dh行号 无返回值
print_num_with_spilt:
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp
        push es

        ;以下利用栈生成局部变量
        mov bp,sp
        sub sp,6
        mov word ptr [bp-2],0
        mov word ptr [bp-4],0
        mov word ptr [bp-6],0


        ;以下确定每行开头的显存地址位置
        mov ax,0b800h
        mov es,ax
        mov al,160
        mul dh
        mov si,ax
        mov cx,10
        mov bx,0
        
        ;以下确定每个字符的举例（10个数字，每行能显示80个，所以8个字符的距离）
        ;每个字符两个字节，所以*16
@@pp1:   mov al,16
        mul bl
        mov di,si
        add di,ax;

        ;以下确定数字的正负，并利用/10法拿到每一位
        push cx
        mov word ptr [bp-2],0
        mov ax,[bx+offset array]
        test al,80h
        jz @@pp5
        mov byte ptr es:[di],'-'
        add di,2
        neg al;拿到绝对值

     
@@pp5:   mov ah,0
        mov dl,10
        div dl
        push ax;商 余数
        inc word ptr [bp-2];记录有几位
        cmp al,0
        je @@pp4 ;结束
        jmp short @@pp5

        ;以下负责把刚刚倒序放入堆栈的每个位数取出，成为正序，并显示
@@pp4:   mov cx,[bp-2]
@@pp6:   pop ax
        add ah,30h;数字变对应的ascii +30h即可
        mov es:[di],ah
        add di,2
        loop @@pp6         
        
        ;显示完一个数字后显示分隔符','
        mov byte ptr es:[di],','
        inc bx
        
        pop cx
        loop @@pp1

        mov sp,bp

        pop es;push  ax 00   pop ax 00
        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
 ;显示array序列，由排序函数每次消除一个逆序对时调用，可以对比看出交换了那两个元素 输入
 ;dh行号 无返回值
print_num:
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp
        push es

        ;以下利用栈生成局部变量
        mov bp,sp
        sub sp,6
        mov word ptr [bp-2],0
        mov word ptr [bp-4],0
        mov word ptr [bp-6],0


        ;以下确定每行开头的显存地址位置
        mov ax,0b800h
        mov es,ax
        mov al,160
        mul dh
        mov si,ax
        mov cx,10
        mov bx,0
        
        ;以下确定每个字符的举例（10个数字，每行能显示80个，所以8个字符的距离）
        ;每个字符两个字节，所以*16
@@p1:   mov al,16
        mul bl
        mov di,si
        add di,ax;

        ;以下确定数字的正负，并利用/10法拿到每一位
        push cx
        mov word ptr [bp-2],0
        mov ax,[bx+offset array]
        test al,80h
        jz @@p5
        mov byte ptr es:[di],'-'
        add di,2
        neg al;拿到绝对值

     
@@p5:   mov ah,0
        mov dl,10
        div dl
        push ax;商 余数
        inc word ptr [bp-2];记录有几位
        cmp al,0
        je @@p4 ;结束
        jmp short @@p5

        ;以下负责把刚刚倒序放入堆栈的每个位数取出，成为正序，并显示
@@p4:   mov cx,[bp-2]
@@p6:   pop ax
        add ah,30h;数字变对应的ascii +30h即可
        mov es:[di],ah
        add di,2
        loop @@p6         

        inc bx
        
        pop cx
        loop @@p1

        mov sp,bp

        pop es;push  ax 00   pop ax 00
        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
 ;选择排序，无参数输入，无返回值
select_sort:
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp
        
        ;以下利用栈产生3个局部变量并初始化
        mov bp,sp
        sub sp,6
        mov word ptr [bp-2],0;临时保存每一扫描时的当前最小值
        mov word ptr [bp-4],0;每一次扫描时的开始位置（也就是还时无序的序列的起始位置）
        mov word ptr [bp-6],0;当前最小值所在位置
        
        ;选择排序每次选一个最小的到前面，共需选9次
        mov cx,9
        mov word ptr [bp-4],0
@@s1:   mov byte ptr [bp-2],127;初始化最小
        mov ax,[bp-4]
        mov [bp-6],ax;初始化最小值所在位置为无序序列开始的位置
        push cx
        mov cx,10
        sub cx,word ptr [bp-4]
        mov bx,[bp-4];从无序序列开始的位置开始扫描最小值
@@s2:   mov al,[offset array+bx]
        cmp al,byte ptr [bp-2]
        jge @@s3;如果大于或者等于就跳过，也就是只比最小值还小才执行下面
        mov byte ptr [bp-2],al;更新最小值
        mov [bp-6],bx;记录下最小值所在位置，方便后面交换
@@s3:   inc bx
        loop @@s2;扫面一次完成后
        mov bx,[bp-4];无序序列最前方
        mov ah,[offset array+bx];保存无序序列最前方那个数
        mov al,[bp-2]
        mov [offset array+bx],al;更新为最小值
        mov bx,[bp-6]
        mov [offset array+bx],ah;交换
        inc word ptr [bp-4]
        pop cx

        push dx
        mov dx,18
        sub dx,cx
        mov dh,dl
        call print_num
        pop dx

        loop @@s1

        mov sp,bp
        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
 ;快速排序，有两个参数 利用堆栈传入，先push的是待排序列的左边界索引L  后push右边界的索引R
 ;无返回值
quick_sort:;
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp
        
        ;以下利用堆栈创建并初始化局部变量
        mov bp,sp;根据入栈顺序推算 [bp+18]是传入的R [bp+20]是传递的L，
        sub sp,14
        mov word ptr [bp-2],0;pivot主元，取 array[L] array[M] array[R]三者的中位数,其中M=（L+R）/2
        mov word ptr [bp-4],0;i 左扫描边界
        mov word ptr [bp-6],0;j 右扫描边界
        mov word ptr [bp-8],0;当前L-R的长度
        mov word ptr [bp-10],0;temp1 
        mov word ptr [bp-12],0;temp2
        mov word ptr [bp-14],0;temp3

        ;以下检测待排长度，不大于2 不需要快排
        mov ax,[bp+18]
        sub ax,[bp+20]
        inc ax
        mov [bp-8],ax
        cmp ax,2
        jna near ptr @@q1

        ;以下将三个候选元素放入temp1 temp2 temp3
        mov bx,[bp+20]
        mov al,[offset array+bx]
        mov byte ptr [bp-10],al;储存最左边元素

        mov bx,[bp+18]
        mov al,[offset array+bx]
        mov byte ptr [bp-14],al;储存右边元素

        mov ax,[bp+20]
        add ax,bx
        mov bl,2;
        div bl
        mov ah,0
        mov di,ax;di保存中间的索引
        mov al,[offset array+di]
        mov byte ptr [bp-12],al;最中间元素

        ;以下开始对temp1 2 3 排序
        cmp al,[bp-14];最右边和中间对比
        jle @@q8;如果满足右边大于中间
        mov ah,[bp-14]
        mov [bp-12],ah
        mov [bp-14],al

@@q8:   mov al,[bp-12]
        cmp al,[bp-10];al指向中间
        jge @@q11
        mov al,[bp-10];记录长度37,89,-100
        cmp al,[bp-14]
        jge @@q10
        mov ah,[bp-12]
        mov [bp-10],ah
        mov [bp-12],al
        jmp short @@q11

@@q10:  mov al,[bp-10]
        mov ah,[bp-12]  ;al指向左 ah指向中间 dl指向右边 但是现在左》右》中，要交换位置
        mov dl,[bp-14]
        mov [bp-14],al
        mov [bp-12],dl
        mov [bp-10],ah
        jmp short @@q11

        ;由于跳转距离太远，用一个中间跳转作为接力
@@q1:   jmp near ptr @@q7

        ;至此temp1《temp2 《temp3排序完成，分别写回array[L] array[M] array[R]
@@q11:  mov al,[bp-10]
        mov bx,[bp+20]
        mov [offset array+bx],al

        mov al,[bp-14]
        mov bx,[bp+18]
        mov [offset array+bx],al

        mov al,[bp-12]
        mov [offset array+di],al
        mov [bp-2],al;储存主元17,5,6

        ;将array[R-1]和 array[M]交换
        mov bx,[bp+18]
        dec bx
        mov ah,[offset array+bx]
        mov [offset array+bx],al
        mov [offset array+di],ah;交换r-1和m处的位置


        ;初始化扫描指针 i,j
        mov ax,[bp+20]
        inc ax
        mov [bp-4],ax;左边界+1

        mov ax,[bp+18]
        sub ax,2;右边界-2
        mov [bp-6],ax

        ;以下是左扫描
@@q3:   mov bx,[bp-4]
        mov al,[offset array+bx]
        cmp al,[bp-2]
        jge @@q2;如果不小于就跳出
        inc word ptr [bp-4]
        loop @@q3;17,5,6,28

        ;以下是右扫描
@@q2:   mov bx,[bp-6]
        mov al,[offset array+bx]
        cmp al,[bp-2]
        jle @@q4;不大于就跳出
        dec word ptr [bp-6]
        loop @@q2


        ;左边第一个大于pivot和右边第一个小于pivot出现了
@@q4:   mov ax,[bp-4]
        cmp ax,[bp-6]
        jnb @@q5;i>=j说明扫描完成了
        ;i<j 交换即可
        mov bx,[bp-4]
        mov al,[offset array+bx]
        

        mov si,[bp-6]
        mov ah,[offset array+si]
        mov [offset array+bx],ah
        mov [offset array+si],al;交换一对逆序对
        
        push dx;显示交换后的结果
        mov dx,ds:[0ah]
        mov dh,dl
        call print_num
        inc dx
        mov ds:[0ah],dx
        pop dx

        inc word ptr [bp-4]
        dec word ptr [bp-6]

        loop @@q3

        ;整个序列扫描完了
@@q5:   mov bx,[bp-4]
        mov al,[offset array+bx]
        mov si,[bp+18]
        dec si
        mov ah,[offset array+si]
        mov [offset array+bx],ah
        mov [offset array+si],al

        push dx;显示交换后的结果
        mov dx,ds:[0ah]
        mov dh,dl
        call print_num
        inc dx
        mov ds:[0ah],dx
        pop dx

        ;至此 本序列 左边小于主元的序列+主元+右边大于主元序列生成完毕
        ;开始递归 z左边的小序列和右边的大序列

        mov ax,[bp+20]
        push ax
        mov ax,[bp-4]
        dec ax
        push ax
        call quick_sort
        pop ax
        pop ax
        
        mov ax,[bp-4]
        inc ax
        push ax
        mov ax,[bp+18]
        push ax
        call quick_sort
        pop ax
        pop ax

        jmp short @@q6

        ;以下是R-L+1 即待排序长度不大于2的情况
@@q7:   cmp word ptr [bp-8],1
        jna @@q6;如果也不大于1 即直接返回
        ;即长度为2 比较两个大小排序
        mov bx,[bp+20]
        mov al,[offset array+bx]
        mov si,[bp+18]
        mov ah,[offset array+si]
        cmp al,ah
        jna @@q6
        mov [offset array+si],al
        mov [offset array+di],ah

        jmp short @@q6

@@q6:   mov sp,bp
        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret


 ;============================================================================
;插入排序
insert_sort:
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp
        
        mov bp,sp
        sub sp,6
        mov word ptr [bp-2],0
        mov word ptr [bp-4],0
        mov word ptr [bp-6],0;三个局部变量初始化

        mov cx,9
        mov bx,1;i
@@i1:   mov al,[offset array+bx]
        mov ah,0
        mov [bp-2],ax;保存array[i]的temp
        mov [bp-4],bx;int j=i
@@i3:   cmp word ptr [bp-4],0
        jna @@i2
        mov si,[bp-4]
        mov ax,[bp-2]
        cmp al,[offset array+si-1]
        jg @@i2
        mov al,[offset array+si-1]
        mov [offset array+si],al
        dec word ptr [bp-4]
        jmp short @@i3
@@i2:   mov al,[bp-2]
        mov si,[bp-4]
        mov [offset array+si],al
        inc bx

        push dx
        mov dx,18
        sub dx,cx
        mov dh,dl
        call print_num
        pop dx

        loop @@i1


        mov sp,bp
        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret

 ;============================================================================
;冒泡排序
buble_sort:
        push ax
        push bx
        push cx
        push dx
        push si
        push di
        push sp
        push bp

        mov cx,9
@@b3:   push cx
        mov bx,0
@@b1:   mov ax,[bx+offset array]
        cmp ah,al
        jge @@b2 ;jge是有符号数判断 如果大于或等于就跳转
        xchg ah,al;如果ah比al小，就要交换了
        mov [bx+offset array],ax
@@b2:   inc bx
        loop @@b1

        

        pop cx

        push dx
        mov dx,18
        sub dx,cx
        mov dh,dl
        call print_num
        pop dx

        loop @@b3

        pop bp
        pop sp
        pop di
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret
        


code ends
end start