微机原理与技术接口实验三循环结构

🌴 2022.5.26 早八实验三

实验三循环结构

1.1 实验要求

熟悉emu8086仿真系统，实现连续地址的内存数据访问，用两种方法实现对五个字从大到小排序

扩展要求：用冒泡法实现快排，计算不同方法的复杂度

1.2 理论分析

选择排序，冒泡排序建议先去搜一下自己熟悉的语言是怎么编写的，看懂算法思路再写汇编会容易很多

选择排序：第一次从R[0]~R[n-1]中选取最大值，与R[0]交换，第二次从R[1]~R[n-1]中选取最大值，与R[1]交换，….，第i次从R[i-1]~R[n-1]中选取最大值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最大值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从大到小排列的有序序列。

排序前：9 3 6 4 2
第一次：9 3 6 4 2
第二次：9 6 3 4 2
第三次：9 6 4 3 2
第四次：9 6 4 3 2

冒泡排序：重复地遍历要排序的数列，第一次比较R[0]~R[n-1]中相邻两个元素是否满足R[i]>R[i+1]如果不满足就交换，第二次比较R[0]~~R[n-2], ….,第n-1次比较R[0]~~R[1]，一共比较n-1次

排序前：2 3 6 4 9
第一次：3 6 4 9 2
第二次：6 4 9 3 2
第三次：6 9 4 3 2
第四次：9 6 4 3 2

扩展要求：冒泡法实现快排，即在冒泡排序的基础上，设置一个标志位，如果当前内循环没有做交换，说明排序正确，直接跳出循环

排序前：9 3 6 4 2
第一次：9 6 4 3 2
第二次：9 6 4 3 2，没有做交换，直接跳出循环结束程序

1.3 汇编语言

💻提示：所有实验源码已在Github整理

选择排序

MOV CX,5-1      ;选择排序，外循环N-1次
MOV BX,OFFSET TAB

LP1:
MOV AX,[BX]     ;取当前TAB[i]给AX
PUSH CX         ;保存数据，CX压栈
MOV SI,BX       ;暂存BX给SI

LP2:
ADD SI,2        ;偏移地址+2转向下一个数
CMP AX,[SI]     ;相邻两个数比较
JAE J1          ;如果AX>[SI]跳转
XCHG AX,[SI]    ;如果AX<[SI]交换，最后一次内循环找到最大数AX

J1:
LOOP LP2        ;继续回到LP2内循环
MOV [BX],AX     ;找到的最大数给[BX]
POP CX
ADD BX,2
LOOP LP1        ;回到外层循环

HLT

TAB DW 9,3,6,4,2   ;段结构使用数据变量放在后面，定义五个数

冒泡排序

MOV CX,5-1      ;冒泡排序，外循环N-1次 

LP1:
PUSH CX
MOV SI,OFFSET TAB   ;当前TAB指针偏移地址给SI

LP2:
MOV AX,[SI]
CMP AX,[SI+2]       ;比较TAB[i]和TAB[i+1]
JAE J1              ;TAB[i]>TAB[i+1]跳转
XCHG AX,[SI+2]      ;TAB[i]<TAB[i+1]交换
MOV [SI],AX

J1:
ADD SI,2            ;SI+2指向下一个数据
LOOP LP2            ;继续下一次内循环
POP CX
LOOP LP1            ;内循环完成，进行外循换
;JMP $

HLT

TAB DW 9,3,6,4,2   ;段结构使用数据变量放在后面，定义五个数

冒泡法快速排序

MOV CX,5-1      ;冒泡法快速排序，外循环N-1次 

LP1:
PUSH CX
MOV SI,OFFSET TAB   ;当前TAB指针偏移地址给SI
MOV BX,0            ;设置标志位如果做交换就+1，如果本次循环没有做交换(BX==0)说明排序正确，跳出内外循环结束程序

LP2:
MOV AX,[SI]
CMP AX,[SI+2]       ;比较TAB[i]和TAB[i+1]
JAE J1              ;TAB[i]>TAB[i+1]跳转
XCHG AX,[SI+2]      ;TAB[i]<TAB[i+1]交换
MOV [SI],AX
ADD BX,1

J1:
ADD SI,2            ;SI+2指向下一个数据
LOOP LP2            ;继续下一次内循环
POP CX
CMP BX,0
JNA J2              ;BX不大于0跳转J2，结束程序运行
LOOP LP1            ;内循环完成，进行外循换
;JMP $

J2:    
HLT

TAB DW 9,3,6,4,2   ;段结构使用数据变量放在后面，定义五个数