-
WinMIPS64下实现冒泡排序(函数调用)
2017-10-08 15:49:59该算法使用冒泡排序法,并且在其中嵌入一个swap函数过程(该算法在课本上有完整的程序,但是其中的数据初始化、寄存器映射、命令的映射以及I/O部分还需要自己手动编写)。编写完成后,在asm.exe中进行检测,然后运行...问题描述:
在这一部分,我们要求编写一个排序算法,对一组int型数据进行排序。该算法使用冒泡排序法,并且在其中嵌入一个swap函数过程(该算法在课本上有完整的程序,但是其中的数据初始化、寄存器映射、命令的映射以及I/O部分还需要自己手动编写)。编写完成后,在asm.exe中进行检测,然后运行。
初始数据要求为:“array: .word 8,6,3,7,1,0,9,4,5,2”
该程序需要对0到10,十个数进行了排序,其中使用了sort和swap两个函数过程,并且swap是嵌套在sort中的,在编写程序的时候一定要注意使用栈来保留寄存器的值,嵌套时还额外需要保存$ra的值。在WinMIPS64运行上述程序。代码实现:
.data after: .asciiz "After sort the array is:\n" before: .asciiz "Before sort the array is:\n" CONTROL: .word 0x10000 DATA: .word 0x10008 SP: .word 0x7ffffffc flag: .word 0 array: .word 8,6,3,7,1,0,9,4,5,2 .text main: daddi r29,r0,SP #r29--$sp ld r16,CONTROL(r0) ld r17,DATA(r0) daddi r8,r0,4 #set string output daddi r9,r0,before #prompt line sd r9,(r17) sd r8,(r16) #print daddi r8,r0,2 #set signed Integer output daddi r1,r0,0 #i<-0 Loop: ld r9,array(r1) #get a[i] sd r9,(r17) sd r8,(r16) #print a[i] daddi r1,r1,8 #i++ daddi r2,r1,-80 beq r2,r0,Exit #if i=10, exit j Loop Exit: daddi r4,r0,array #parameter1 address of a[] daddi r5,r0,10 #parameter2 n jal bubblesort daddi r8,r0,4 #set string output daddi r9,r0,after #prompt line sd r9,(r17) sd r8,(r16) #print daddi r8,r0,2 #set signed Integer output daddi r1,r0,0 #i<-0 Loop3: ld r9,array(r1) #get a[i] sd r9,(r17) sd r8,(r16) #print a[i] daddi r1,r1,8 #i++ daddi r2,r1,-80 beq r2,r0,Exit3 #if i=10, exit j Loop3 Exit3: halt bubblesort: daddi r29,r29,-24 #make room on stack sd $ra,16(r29) sd r16,8(r29) sd r17,0(r29) dadd r22,r4,r0 #get a[] daddi r23,r5,0 #get n and r18,r18,r0 #i=0 fori: slt r10,r18,r23 #if i<n, r10=1 beq r10,r0,exiti #if i>n, jump exiti daddi r19,r18,-1 #j<-i-1 forj: slti r10,r19,0 #if j<0, r10=1 bne r10,r0,exitj #if j<0, jump exitj dsll r11,r19,3 #j*8 dadd r12,r11,r22 #a+j*8 ld r13,0(r12) #a[j] ld r14,8(r12) #a[j+1] slt r10,r14,r13 beq r10,r0,exitj #if a[j+1]>a[j] jump exitj dadd r4,r0,r22 #parameter1 address of a[] daddi r5,r19,0 #parameter2 j jal swap daddi r19,r19,-1 #j-- j forj exitj: daddi r18,r18,1 j fori exiti: ld r17,0(r29) ld r16,8(r29) ld $ra,16(r29) daddi r29,r29,24 #restore stack pointer jr $ra swap: dsll r8,r5,3 #r8=k*8 dadd r8,r4,r8 #r8=a+(k*8) ld r9,0(r8) #r9=a[k] ld r10,8(r8) #r10=a[k+1] sd r10,0(r8) #a[k]=r10 sd r9,8(r8) #a[k+1]=r9 jr $ra
汇编器测试:运行结果:
其实,代码还不是很完善,对于函数调用方面,一些寄存器需要被调用者保存,以免发生数据丢失。
-
常用排序算法(使用C++函数模板编写)
2020-05-25 20:37:35void sort(T a[], int n)//冒泡法排序 { int i, j; T temp; for (i = 1; i < n; i++) { for (j = 0; j < n - i; j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+...1 冒泡排序
template<typename T> void sort(T a[], int n)//冒泡法排序 { int i, j; T temp; for (i = 1; i < n; i++) { for (j = 0; j < n - i; j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }
2 改进后的冒泡排序
template<typename T> //改进后的冒泡排序 void sort(T a[], int n) { bool exchange = true; int i = 1; int j; while (exchange) { exchange = false; for (j = 0; j < n - i; j++) { if (a[j] > a[j + 1]) { T temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; exchange = true; } } i++; } }
3选择排序
template<typename T> void sort(T a[],int n)//选择法排序 { int i, j, k; T temp; for (i=0;i<n-1; i++) { k = i; for (j=i+1; j<n; j++) { if (a[j] > a[k]) k = j; } if (k != i) { temp = a[k]; a[k] = a[i]; a[i] = temp; } } }
4 直接插入排序
template<typename T> void sort(T a[], int n) //直接插入排序 { int i,j; T temp; for (i = 1; i < n; i++) { temp = a[i]; for (j = i-1; j>= 0 && temp < a[j]; j--) { a[j + 1] = a[j]; } a[j+1]=temp; }
5 折半插入排序
template<typename T>//折半插入排序 void sort(T a[],int n) { int i, j; int low, high, mid; for (i = 1; i < n; i++) { T temp; temp = a[i]; low = 0; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (temp < a[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= low; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } }
6 交换法排序
template<typename T> void sort(T a[],int n)//交换法排序 { int i, j; T temp; for (i = 0;i<n-1;i++) { for (j= i + 1;j< n; j++) { if(a[j]>a[i]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } } } }
7 希尔排序
template<typename T> //希尔排序 void sort(T a[], int n) { int i,j,d; for (d=n/2;d>=1;d=d/2) { for (i = d; i < n; i++) { T temp = a[i]; for (j = i - d; j >= 0 && temp < a[j]; j = j - d) { a[j + d] = a[j]; } a[j + d]=a[j]; } } }
8 快速排序
template<typename T> //快排 void sort(T a[], int left, int right) { int i = left; int j = right; T temp = a[left]; T k; if (left > right) return; while (i != j) { while (a[j] >= temp && i < j) { j--; } while (a[i] <= temp && i < j) { i++; } if (i!= j) { k = a[i]; a[i] = a[j]; a[j] = k; } } a[left] = a[i]; a[i] = temp; sort8(a, left, i-1); sort8(a, i + 1, right); }
-
冒泡算法的一点点心得
2013-02-23 15:05:0311、编写子函数:(1)用冒泡法将一个数组排成升序的函数---SUB1;(2)在升序数组中插入一个数,并且保持该数组仍为升序数组的函数---SUB2。 主函数:①输入任意10个正整数给数组;②调用SUB1对数组进行排序;③从...11、编写子函数:(1)用冒泡法将一个数组排成升序的函数---SUB1;(2)在升序数组中插入一个数,并且保持该数组仍为升序数组的函数---SUB2。
主函数:①输入任意10个正整数给数组;②调用SUB1对数组进行排序;③从键盘输入一个正整数,调用SUB2将其插入该数组。
冒泡算法是一种比较简单的算法,其目的是保证大的数在后面,小的数在前面。
本来想搞一个动态数组 int n; scanf("%d",&n); int a[n]; 结果挺奇怪gcc里面编译通过,而在vc里面编译不通过,暂时没想到办法,先用宏定义代替 #define num 10
在SUB2即在数组中插入一个正整数,用到了一点小技巧。如果插入的数从原数组的最小值开始进行比较,后面的操作会比较困难。因此这里选择从原数组最大的数开始进行比较。并且 if(a[i]<b) {a[i+1]=b;break;}进行终止,也就是用break跳出循环语句。
具体代码如下:
#include<stdio.h>
#define num 10
void sub1(int a[],int n)
{
int j,temp,i;
for(j=1;j<n-1;j++)
{
for(i=0;i<n-1;i++)
{
if(a[i]>a[i+1])
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
}void sub2(int a[],int n,int b)
{ int i;
for(i=n-1;i>=0;i--)
{ if(a[i]<b)
{a[i+1]=b;
break;
}
else a[i+1]=a[i];
}
}void main()
{
int k;
int abc[num];
for(k=0;k<num;k++)
{ int i;
printf("please input the %d number",k);
scanf("%d",&i);
abc[k]=i;
}
sub1(abc,num);
int j=0;
for(j;j<num;j++)
{
printf("the number abc[%d] is %d\n",j,abc[j]);
}
sub2(abc,num,4);
j=0;
for(j;j<=num;j++)
{
printf("the number abc[%d] is %d\n",j,abc[j]);
}
} -
冒泡加数组
2019-12-30 23:35:18编写一个函数void minmaxave(int a[ ],int ...但排序时必须根据m的的值选用算法:当m为1时用冒泡法排序; 当m为2时用选择排序; 当m为其他值时不排序。 再编写主函数,先从键盘输入20个数存入一个数组再输出, 然后分...编写一个函数void minmaxave(int a[ ],int n)完成对大小为n的数组找出最大值最小值并输出,
编写一个函数void sort(int a[ ],int n,int m)完成对大小为n的数组从小到大的排序,
但排序时必须根据m的的值选用算法:当m为1时用冒泡法排序;
当m为2时用选择排序;
当m为其他值时不排序。
再编写主函数,先从键盘输入20个数存入一个数组再输出,
然后分别调用上面第一个函数求该组数的最小、最大、平均值,调用第二个函数先排序然后将排序结果输出。#include<stdio.h>
#define n 20int main(){void minmaxavg(int a[], int );void sort(int a[], int , int );int a[n], m, i;for (i = 0;i < n ;i++){scanf("%d", &a[i]);printf("%d “, a[i]);}printf(“请输入m的值:”);scanf(”%d", &m);minmaxavg(a, n);sort( a, n , m);}void minmaxavg(int a[], int N){int avg, max=a[0],min=a[0],sum = 0,i;for (i = 0;i < N;i++){if (max < a[i])max = a[i];else if (min > a[i])min = a[i];sum += a[i];}avg = sum / N ; printf(“它们的和是%d,平均值是%d,其中最大值是%d,最小值是%d\n”, sum, avg, max, min);}void sort(int a[], int N, int m){int j;if (m == 1)//冒泡法{int i, j, t;for (i = 1;i < N;i++)for (j = 0;j < N - i;j++)if (a[j] < a[j + 1])t = a[j], a[j] = a[j + 1], a[j + 1] = t;for (i = 0;i < N;i++)printf("%d “, a[i]);}else if (m == 2)//选择法{int i, pos, min,j;for (i = 0;i < N - 1;i++){min = a[i];pos = i;for (j = i + 1;j < N;j++)if (a[j] < min){min = a[j];pos = j;}a[pos] = a[i];a[i] = min;}printf(“排序后为:”);for (j = 0;j < N;j++)printf(”%d “, a[j]);}else {printf(“由于没有选择排序,所以原样输出:”);for (j = 0;j < N;j++)
printf(”%d ", a[j]);
}
} -
一种高效率的排序方法-归并排序的实现(主要解决matlab中多维数组排序的问题)
2016-08-01 21:07:24对于一般排序来说,如果数据量在100-1000个之间可以选择“冒泡法”进行排序,这种方法容易理解,也容易编写,但是数据量过大时,冒泡法在执行效率上会出现问题。这是就有一种算法复杂程度为:nlogn的排序方法--归并... -
C/C++常用算法手册.秦姣华(带详细书签).pdf
2018-04-15 22:14:354.2.2 冒泡排序算法示例 102 4.3 选择排序法 104 4.3.1 选择排序算法 104 4.3.2 选择排序算法示例 105 4.4 插入排序法 107 4.4.1 插入排序算法 107 4.4.2 插入排序算法示例 108 4.5 Shell排序法 110 4.5.1 ... -
C/C++常用算法手册.秦姣华(有详细书签).rar
2018-04-17 09:05:234.2.2 冒泡排序算法示例 102 4.3 选择排序法 104 4.3.1 选择排序算法 104 4.3.2 选择排序算法示例 105 4.4 插入排序法 107 4.4.1 插入排序算法 107 4.4.2 插入排序算法示例 108 4.5 Shell排序法 110 4.5.1 ... -
数据结构与算法课程C语言上机考试题—2011.docx
2020-12-14 10:13:121从键盘输入 10 个整数用冒泡法对这 10 个数排序由小到大后输出 2从键盘输入 10 个整数用选择法对这 10 个数排序由大到小后输出 3对于一个自然数 如果该数的所有因子之和正好等于该数 则该数称为完数 统计 1000 以内... -
谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar
2013-06-13 22:35:214.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数) 56 4.5.2 scanf函数(格式输入函数) 58 顺序结构程序设计举例 60 45 分支... -
【20200326】【每天一道算法题】移动零(数组)
2020-03-26 13:35:59问题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。...# 方法一:类似于冒泡排序法的冒泡思想 # 思路:循环次数为len(nums)-1,如果遇到0,那么交换比较的这两个相邻元... -
常用算法程序集(C语言第三版)只要2个积分
2008-01-30 13:55:41分布函数 14.11 χ-分布函数 14.12 F-分布函数 14.13 正弦积分 14.14 余弦积分 14.15 指数积分 14.16 第一类椭圆积分 14.17 第二类椭圆积分 第15章 排序 15.1 冒泡排序 15.2 快速排序... -
折半查找(二分查找)
2020-12-18 09:10:27利用C语言阶段学过的排序算法,进行排序。之后输入带查找的数据x,利用折半查找算法进行查找,找到则输出该数的位置及查找次数,否则输出“0”和查找次数。 首先利用冒泡法进行从小大排序,再进行二分查找。 注意:题... -
数组的学习总结
2017-10-29 17:30:00本周主要学习了关于一维数组的应用,二分查找法,冒泡排序法,指针法访问数组元素,数组名和指针作函数参数,在数组中插入和删除元素,合并两个有序数组,编写出用于查找和排序的函数,动态存储管理与动态数组的实现... -
大话数据结构
2019-01-10 16:35:22作品目录编辑 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。...7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一个轮子要0.5天、造... -
大话数据结构 程杰
2018-09-01 10:06:43目录: 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。...7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一个轮子要0.5天、造一... -
大话数据结构(中文高清版)
2017-04-19 11:57:092.7.1 事后统计方法 24 2.7.2 事前分析估算方法 25 2.8 函数的渐近增长 27 2.9 算法时间复杂度 29 理解大O推导不算难,难的其实是对数列的一些相关运算,这考察的更多的是数学知识和能力。 2.9.1 算法时间复杂度... -
大话数据结构三个版本
2018-09-10 09:39:38如果你教某人如何编写程序,你将折磨他一辈子。 1.2你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:“你数据结构是怎么学的?” 1.3数据结构起源 4 1.4基本... -
《大话数据结构》( 程杰 编著)
2018-02-15 10:00:21如果你教某人如何编写程序,你将折磨他一辈子。 1.2你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:“你数据结构是怎么学的?” 1.3数据结构起源 4 1.4基本... -
大话数据结构-程杰
2014-07-13 23:45:52如果你教某人如何编写程序,你将折磨他一辈子。 1.2 你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:"你数据结构是怎么学的?" 1.3 数据结构起源 4 1.4 ... -
传智播客扫地僧视频讲义源码
2019-04-03 21:54:2218_浅拷贝问题解决_深拷贝_显示编写拷贝构造函数 19_深拷贝和浅拷贝_默认的等号操作符也是浅拷贝_传智扫地僧 20_构造函数的初始化列表 21_强化训练1_构造和析构调用顺序 22_强化训练2_匿名对象生命周期 23_强化训练3... -
并行计算导论(原书第2版).[美]Ananth Grama(带详细书签).pdf
2018-04-24 21:31:359.6 其他排序算法 9.6.1 枚举排序 9.6.2 基数排序 9.7 书目评注 习题 第10章 图算法 10.1 定义和表示 10.2 最小生成树:Prim算法 10.3 单源最短路径:Dijkstra算法 10.4 全部顶点对间的最短路径 10.4.1 ... -
数据结构实验
2012-04-13 09:55:47实验7:至少三种排序算法的程序实现 (第十六周星期三7、8节) 一、 实验目的 1.掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。 2.对各种查找、排序技术的时间、空间复杂性有... -
C语言进阶:重点、难点与疑点解析.牟海军(带详细书签) PDF 下载 高清 完整版
2018-01-11 23:34:54透析C语言中的核心概念、重要知识点、不易理解的知识...11.2 冒泡法排序/329 11.3 选择法排序/332 11.4 快速排序/334 11.5 归并排序/337 11.6 顺序查找/340 11.7 二分查找/341 附录 如何养成良好的编程习惯/344 -
C++大学教程,一本适合初学者的入门教材(part2)
2009-09-20 15:15:4220.5.6 基本查找与排序算法 20.5.7 swap、iter_swap和swap_ranges 20.5.8 copy—backward、 merge、 unique和reverse 20.5.9 inplace_merge、 unique—copy和reverse—copy 20.5.10 集合操作 20.5.11 1... -
当开发者在编写Lambda表达式时,也会随之被编译成一个函数式接口。 -> 是Java 8新增的Lambda表达式中,变量和临时代码块的分隔符,即: (变量) -> {代码块} 如果代码块只有一个表达式,大括号可以省略。如果...
-
C++程序员面试宝典
2013-04-01 13:36:1913.7 排序算法的总结 180 第14章 软件工程(教学视频:39分钟) 182 14.1 软件工程基础 182 面试题158 什么是软件工程 182 面试题159 什么是软件危机 183 14.2 软件的4大开发模型 184 面试题160 4大开发模型的区别 ... -
郝斌C语言教程全套视频180集下载地址
2012-09-21 22:27:01163_冒泡排序 162_结构体10_结构体变量的运算 161指针优点大总结【重点】 160_结构体9_应该发送内容还是应该发送地址【重点】 159_结构体8_通过函数完成对结构体变量的输入和输出 158_结构体7_复习上节课知识 157_... -
c语言经典案例
2014-10-30 08:06:57实例021 冒泡排序 26 实例022 快速排序 27 实例023 选择排序 28 实例024 归并排序 29 实例025 二分查找 31 实例026 分块查找 32 实例027 哈希查找 34 实例028 斐波那契数列 37 实例029 哥德巴赫猜想 38 实例030 尼科... -
数据结构课设
2013-01-03 02:51:255、排序算法比较 任务 :利用随机函数产生10个样本(其中之一已为正序,之一为倒序),每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序(递归和非递归),...
-
基于Qt的LibVLC开发教程
-
python Flask+scrapy+人工智能 实现高性能搜索引擎
-
类与对象的小结 java 1614782140
-
【爱码农】C#制作MDI文本编辑器
-
Galera 高可用 MySQL 集群(PXC v5.6 + Ngin
-
python 下载文件
-
DOM
-
MySQL 高可用工具 heartbeat 实战部署详解
-
《文件和目录操作命令》
<2.> -
如何在VS中克隆GitHub库
-
电风扇沙
-
janus-client:cc ++ webrtc本机janus客户端Qt opengl视频会议视频室视频通话文本室会议聊天-源码
-
极米科技 极米科技首次公开发行股票并在科创板上市招股意向书.pdf
-
C Primer Plus --第十二章 存储类,链接 和 内存管理
-
Windows系统管理
-
C++新手自己写的高效分解质因数
-
信息学奥赛一本通-教程PPT课件(第五版)算法部分 第七章 分治算法.pdf
-
MySQL Router 实现高可用、负载均衡、读写分离
-
Petri网在井下机车调度中的建模与仿真.pdf
-
实现 MySQL 读写分离的利器 mysql-proxy