问题描述：
在这一部分，我们要求编写一个排序算法，对一组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








汇编器测试：




运行结果：






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




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对数组进行排序；③从键盘输入一个正整数，调用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]);

 }

}

 

编写一个函数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]);

}

}