对于归并排序算法的概念已经介绍这里就不再赘述,直接附上代码实现 在代码中已经标注了具体的实现
#include<stdio.h> #include<assert.h> #include<iostream> #include<string.h> using namespace std; #define MAX_SIZE 20 /* *代码中多次出现assert()函数 于是查了一下assert函数的用法 *assert的作用是先计算表达式 expression ，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。 */ typedef struct { int a[MAX_SIZE];//用于储存排序数组 int size;//用于记录顺序表的长度 }seqlist; //顺序表初始化 void init_list(seqlist *l); //尾插 void last_insert(seqlist *l, int n); //读取数组中第n个元素的值 void read(seqlist *l, int n); //把第i个数改为m void change(seqlist *l, int i, int m); //打印顺序表 void print(seqlist *l); //找到数为n在数组中的下标位置 void find(seqlist *l, int n); //在第i个位置上插入数字n int insert(seqlist *l, int i, int n); //交换数组中下标为i和j的值 void swap(seqlist *l,int i,int j); void Merge(int SR[],int TR[],int i ,int m,int n); void MSort(int SR[],int TR[],int s,int t ); void MergeSort(seqlist*l); #include"SeqList.h" #include<iostream> using namespace std; #define MAX_SIZE 20 //顺序表初始化 void init_list(seqlist *l) { assert(l);//判断l是否为空 memset(l->a, 0, sizeof(l->a));//初始化数组 l->size = 0; } //尾插 void last_insert(seqlist *l, int n) { assert(l); if (l->size < MAX_SIZE) { l->size++;//总数加1 l->a[l->size] = n;//现在下标变成从1开始 然后尾部插入法就是将n赋值给a[l->size] } else { cout << "空间不足" << " "; } } //读取数组中第n个元素的值 void read(seqlist *l, int n) { assert(l); if (n <= l->size) std::cout << n << ":" << l->a[n ] << " "; } //把第i个数改为m void change(seqlist *l, int i, int m) { assert(l); l->a[i] = m; } //打印顺序表 void print(seqlist *l) { assert(l); for (int i = 1; i <= l->size; i++) printf("%d ", l->a[i]); } //找到数为n在数组中的下标位置 void find(seqlist *l, int n) { assert(l); for (int i = 1; i <= l->size; i++) { if (l->a[i] == n) printf("数组下标为%d的等于%d ", i,n); } } //在第i个位置上插入数字n int insert(seqlist *l, int i, int n) { if (i<1 || i>l->size) { cout << "插入位置不对" << " "; return -1; } if (l->size == MAX_SIZE) { cout << "存储空间不足" << " "; return -1; } l->size++;//总个数再加一 for (int j = l->size; j > i; j--) { //数组整体后移 l->a[j-1] = l->a[j]; } //把下标位置为i-1的位置空出来 再赋值 l->a[i] = n; return 0; //return 1和return 0? } //交换数组中下标为i和j的值 void swap(seqlist *l,int i,int j){ int temp=l->a[i]; l->a[i]=l->a[j]; l->a[j]=temp; } //将SR[ii..m]和SR[m+1...n]归并为有序的TR[i..n] void Merger(int SR[],int TR[],int i,int m,int n){ int j,k,l; for(j=m+1,k=i;i<=m&&j<=n;k++)//将SR中记录由小到大归并入TR { if(SR[i]<SR[j]) TR[k]=SR[i++]; else TR[k]=SR[j++]; } if(i<=m){ for(l=0;l<=m-i;l++) TR[k+l]=SR[i+l];//将剩余的SR[i...m]复制到TR } if(j<=n) { for(l=0;l<=n-j;l++) TR[k+l]=SR[j+l];//将剩余的代码复制到SR[j...n]复制到TR } } void MSort(int SR[],int TR1[],int s,int t){ int m; int TR2[MAX_SIZE+1]; if(s==t) TR1[s]=SR[s]; else{ m=(s+t)/2;//将SR[s...t]平分为SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m);//递归将SR[s..m]归并为有序的TR2[s..m] MSort(SR,TR2,m+1,t);//递归将SR[m+1..t]归并为TR2[m+1..t] Merger(TR2,TR1,s,m,t);//将TR2[s..m]和TR[m+1..t] } } void MergeSort(seqlist *l){ MSort(l->a,l->a,1,l->size); } #include"SeqList.h" int main() { int n; seqlist l; init_list(&l); last_insert(&l, 50); last_insert(&l, 10); last_insert(&l, 90); last_insert(&l, 30); last_insert(&l, 70); last_insert(&l, 40); last_insert(&l, 80); last_insert(&l, 60); last_insert(&l, 20); print(&l); printf("\n"); MergeSort(&l); print(&l); return 0; }归并算法排序使用大量的递归,虽然在代码理解上比较简单,但是会造成时间和空间上的浪费,于是我们考虑将递归转换成迭代 ,也就是我们用到的非递归算法 在文件中加入
void MergePass(int SR[],int TR[],int s,int n); void MergeSort1(seqlist *l);在函数实现中加入
void MergePass(int SR[],int TR[],int s,int n){ int i=1; int j; while(i<=n-2*s+1){ Merge(SR,TR,i,i+s-1,i+2*s-1);//亮亮归并 i=i+2*s; } if(i<n-s+1)//归并最后两个序列 Merge(SR,TR,i,i+s-1,n); else for(j=i;j<=n;j++) TR[j]=SR[j]; } void MergeSort1(seqlist *l) { int *TR=(int *)malloc(l->size*sizeof(int));//申请额外的空间 int k=1; while(k<l->size){ MergePass(l->a,TR,k,l->size); k=2*k; MergePass(TR,l->a,k,l->size); k=2*k; } }在归并排序算法的基础上就可以运行了
