精华内容
下载资源
问答
  • 算法使用冒泡排序法,并且在其中嵌入一个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
    
    
    
    



    汇编器测试:



    运行结果:




    其实,代码还不是很完善,对于函数调用方面,一些寄存器需要被调用者保存,以免发生数据丢失。


    
    展开全文
  • 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 冒泡排序

    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);
    }
    
    
    展开全文
  • 11、编写函数:(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]);
    }
    }

    展开全文
  • 对于一般排序来说,如果数据量在100-1000个之间可以选择“冒泡法”进行排序,这种方法容易理解,也容易编写,但是数据量过大时,冒泡法在执行效率上会出现问题。这是就有一种算法复杂程度为:nlogn的排序方法--归并...
  • 4.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 ...
  • 4.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 ...
  • 1从键盘输入 10 个整数用冒泡法对这 10 个数排序由小到大后输出 2从键盘输入 10 个整数用选择法对这 10 个数排序由大到小后输出 3对于一个自然数 如果该数的所有因子之和正好等于该数 则该数称为完数 统计 1000 以内...
  • 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数) 56 4.5.2 scanf函数(格式输入函数) 58 顺序结构程序设计举例 60 45 分支...
  • 问题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。...# 方法一:类似于冒泡排序法冒泡思想 # 思路:循环次数为len(nums)-1,如果遇到0,那么交换比较的这两个相邻元...
  • 分布函数 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天、造一...
  • 2.7.1 事后统计方法 24 2.7.2 事前分析估算方法 25 2.8 函数的渐近增长 27 2.9 算法时间复杂度 29 理解大O推导不算难,难的其实是对数列的一些相关运算,这考察的更多的是数学知识和能力。 2.9.1 算法时间复杂度...
  • 如果你教某人如何编写程序,你将折磨他一辈子。 1.2你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:“你数据结构是怎么学的?” 1.3数据结构起源 4 1.4基本...
  • 如果你教某人如何编写程序,你将折磨他一辈子。 1.2你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:“你数据结构是怎么学的?” 1.3数据结构起源 4 1.4基本...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    如果你教某人如何编写程序,你将折磨他一辈子。 1.2 你数据结构怎么学的? 3 他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:"你数据结构是怎么学的?" 1.3 数据结构起源 4 1.4 ...
  • 18_浅拷贝问题解决_深拷贝_显示编写拷贝构造函数 19_深拷贝和浅拷贝_默认的等号操作符也是浅拷贝_传智扫地僧 20_构造函数的初始化列表 21_强化训练1_构造和析构调用顺序 22_强化训练2_匿名对象生命周期 23_强化训练3...
  • 9.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语言中的核心概念、重要知识点、不易理解的知识...11.2 冒泡法排序/329 11.3 选择法排序/332 11.4 快速排序/334 11.5 归并排序/337 11.6 顺序查找/340 11.7 二分查找/341 附录 如何养成良好的编程习惯/344
  • 20.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:19
    13.7 排序算法的总结 180 第14章 软件工程(教学视频:39分钟) 182 14.1 软件工程基础 182 面试题158 什么是软件工程 182 面试题159 什么是软件危机 183 14.2 软件的4大开发模型 184 面试题160 4大开发模型的区别 ...
  • 163_冒泡排序 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:25
    5、排序算法比较 任务 :利用随机函数产生10个样本(其中之一已为正序,之一为倒序),每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序(递归和非递归),...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

编写冒泡法排序算法函数